A coloring of edges is called proper if adjacent edges are assigned different colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. The acyclic chromatic index and its vertex analogue can be used to bound other parameters like oriented chromatic number and star chromatic number of a graph, both of which have many practical applications, as in wavelength routing in optical networks and statistical mechanics in enumerating the number of statistical mechanical diagrams.

The problem of eliminating all cycles in a graph by removing a set of vertices goes back at least to the work of Kirchhoff on spanning trees. Determining the decycling number of a graph is equivalent to finding the greatest order of an induced forest in G. The problem of determining the decycling number ∇(G) of a network G is NP-complete even for planar graphs, bipartite graphs and perfect graphs.

A minimum decycling set in a Wavelength Division Multiplexing Network,

sets up routes between given pairs of nodes in the network and determines the minimum number of wavelength converters that are used in order to reduce the number of wavelengths used to set up the communications. Decycling sets also have applications in combinatorial circuit designs, deadlock prevention in operating systems, monopolies in synchronous distributed systems, constraint satisfaction problem and bayesian inference in artificial intelligence, and VLSI chip design.

Copyright © 2020 SYNERGIES IN COMPUTATIONAL, MATHEMATICAL, STATISTICAL AND PHYSICAL SCIENCES (FIM 2020 : SCMSPS 2020) - All Rights Reserved.