Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms

Journal title

Archives of Control Sciences




No 3

Publication authors

Divisions of PAS

Nauki Techniczne


<jats:title>Abstract</jats:title> <jats:p>In many applications in sequencing and scheduling it is desirable to have an underlaying graph as equitably colored as possible. In this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs.</jats:p>


Committee of Automatic Control and Robotics PAS




ISSN 1230-2384


Chen (1120), Equitable andm - bounded coloring of split graphs InCombinatorics and Computer Springer, Science. ; Zhuand (2008), Equitable list colorings of planar graphs without short cycles, Theoret Comput Sci, 407. ; Chen (1994), Equitable coloring and the maximum degree, Combinatorics, 15, 443, ; 9 (1964), Problem In editor Theory of Graphs and its Applications, Czech Acad Sci Publ, 159. ; Kiersteadand (2008), A short proof of the Hajnal - Szemeredi theorem on equitable colouring Probability and, Combinatorics Computing, 17, 265. ; Furmańczyk (2013), Equitable coloring of corona products of graphs, Adv Appl Disc Math, 11, 103. ; Bodleanderand (2005), Equitable colorings of bounded treewidth graphs, Theor Comput Sci, 349. ; Kierstead (2010), A fast algorithm for equitable coloring, Combinatorica, 30, 217, ; Chenand (2012), Equitable Δ - coloring of graphs, Disc Math, 312. ; Meyer (1973), Equitable coloring, Amer Math Monthly, 80, 920, ; Lam (2001), On the equitable chromatic number of completen - partite graphs, Disc Appl Math, 113. ; Furmańczykand (2016), Equitable coloring of corona products of cubic graphs is harder than ordinary coloring Ars Mathematica, Contemporanea, 10, 333. ; Lihand (1996), On equitable coloring of bipartite graphs, Disc Math, 151. ; Yapand (1997), The equitable Δ - coloring conjecture holds for outerplanar graphs Bulletin of the Inst of Math Academia, Sinica, 25, 143. ; Hajnaland (1970), Proof of a conjecture of Erdos InCombinatorial Theory and Its Applications , II North Amsterdam, Colloq Math Soc, 4. ; Goluch (2015), Koala graph theory internet service TASK, Quarterly, 19, 455. ; Wangand (2000), Equitable colorings of line graphs and completer - partite graphs Systems Science and Mathematical, Sciences, 13, 190. ; Nakprasitand (2012), Equitable colorings of planar graphs without short cycles, Theoret Comput Sci, 465. ; Yapand (1998), Equitable colourings of planar graphs, Comb Math Comb Comput, 27, 97. ; Grimmetand (1975), On coloring random graphs Cambridge Philos, Math Proc Soc, 77. ; Kaliraj (2012), Equitable coloring on corona graph of graphs, Comb Math Comb Comput, 81. ; Kubale (1989), Interval vertex - coloring of a graph with forbidden colors, Disc Math, 74. ; Linand (2010), - Equitable colorings of Kronecker products of graphs, Disc Appl Math, 158. ; Kiersteadand (2010), Equitable versus nearly equitable coloring and the Chen conjecture, Combinatorica, 30, 201, ; Nakprasit (2012), Equitable colorings of planar graphs with maximum degree at least nine, Disc Math, 312. ; Linand (2012), - Equitable colorings of Cartesian products of graphs, Disc Appl Math, 160.