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

• Autorzy: Furmańczyk H. , Jastrzębski A. , Kubale M.

Identyfikatory

DOI

10.1515/acsc-2016-0016

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

computer experiments; corona graph; equitable chromatic number; equitable coloring conjectures; NP-hardness; polynomial heuristics

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2016
• Tom: Vol. 26, no. 3
• Strony: 281--295
• Opis fizyczny: Bibliogr. 37 poz.,

Twórcy

autor

Furmańczyk H.

• Institute of Informatics, Gdańsk University of Technology, Wita Stwosza 57, 80-952 Gdańsk, Poland

autor

Jastrzębski A.

• Department of Algorithms and System Modeling, Gdańsk University of Technology, Narutowicza 11/12, 80-233 Gdańsk, Poland

autor

Kubale M.

• Department of Algorithms and System Modeling, Gdańsk University of Technology, Narutowicza 11/12, 80-233 Gdańsk, Poland

Bibliografia

• [1] N. Alon and R. Yuster: H-factors in dense graphs. J. Combin. Theory Ser. B, 66 (1996), 269-282.
• [2] H. L. Bodleander and F. V. Fomin: Equitable colorings of bounded treewidth graphs. Theor. Comput. Sci., 349(1), (2005), 22-30.
• [3] B. L. Chen and K. W. Lih: Equitable coloring of trees. J. Combin. Theory Ser. B, 61 (1994), 83-87.
• [4] B. L. Chen and Ch.H. Yen: Equitable Δ-coloring of graphs. Disc. Math., 312 (2012), 1512-1517.
• [5] B. L. Chen, K.W. Lih and P. L. Wu: Equitable coloring and the maximum degree. Europ. J. Combinatorics, 15 (1994), 443-447.
• [6] B. L. Chen, M. T. Ko and K. W. Lih: Equitable and m-bounded coloring of split graphs. In Combinatorics and Computer Science, LCNS 1120, Springer, 1995.
• [7] B. L. Chen, K. W. Lih and Ch. H. Yen: Equivalence of two conjectures on equitable coloring of graphs. J. Combinatorial Optimization, 25(4), (2013), 501-504.
• [8] P. Erdös. Problem 9. In M. Fielder, editor, Theory of Graphs and its Applications. Czech. Acad. Sci. Publ., Prague, 1964. Vol. 159.
• [9] R. Fidytek, H. Furmańczyk and P. Żyliński: Equitable coloring of Kneser graphs. Discussiones Mathematicae Graph Theory, 29(1), (2009), 119-142.
• [10] H. Furmańczyk: Graph Colorings, chapter Equitable coloring of graphs. American Mathematical Society Providence, Rhode Island, 2004.
• [11] H. Furmańczyk: Equitable coloring of graph products. Opuscula Mathematica, 26(1), (2006), 31-44.
• [12] H. Furmańczyk and M. Kubale: Equitable coloring of corona products of cubic graphs is harder than ordinary coloring. Ars Mathematica Contemporanea, 10(2), (2016), 333-347.
• [13] H. Furmańczyk, M. Kubale and V. Mkrtchyan: Equitable colorings of corona multiproducts of graphs. arXiv:1210.6568, 2012.
• [14] H. Furmańczyk, K. Kaliraj, M. Kubale and V.J. Vivin: Equitable coloring of corona products of graphs. Adv. Appl. Disc. Math., 11(2), (2013), 103-120.
• [15] T. Goluch, K.M. Ocetkiewicz and K. Giaro: Koala graph theory internet service. TASK Quarterly, 19(4), (2015), 455-470.
• [16] G. R. Grimmet and C. McDiarmid: On coloring random graphs. Math. Proc. Cambridge Philos. Soc., 77 (1975), 313-324.
• [17] A. Hajnal and E. Szemerédi: Proof of a conjecture of Erdos. In Combinatorial Theory and Its Applications, II. Colloq. Math. Soc. Janos Bolyai, Vol. 4, North-Holland, Amsterdam, 1970.
• [18] S. Janson and A. Ruciński: The infamous upper tail. Random Structures and Algorithms, 20 (2001), 317-342.
• [19] K. Kaliraj, V. J. Vivin and V. J. Vivik: Equitable coloring on corona graph of graphs. J. Comb. Math. Comb. Comput., 81 (2012), 191-197.
• [20] H. A. Kierstead and A. V. Kostochka: An Ore-type theorem on equitable coloring. J. Combin. Theory Ser. B, 98 (2008), 226-234.
• [21] H. A. Kierstead and A. V. Kostochka: A short proof of the Hajnal-Szemeredi theorem on equitable colouring. Combinatorics, Probability and Computing, 17(2), (2008), 265-270.
• [22] H. A. Kierstead and A. V. Kostochka: Equitable versus nearly equitable coloring and the Chen-Lih-Wu conjecture. Combinatorica, 30(2), (2010), 201-216.
• [23] H. A. Kierstead, A. V. Kostochka, M. Mydlarz and E. Szemerédi: A fast algorithm for equitable coloring. Combinatorica, 30(2), (2010), 217-224.
• [24] A. Kosowski and K. Manuszewski: Graph Colorings, chapter Classical coloring of graphs. American Mathematical Society Providence, Rhode Island, 2004.
• [25] M. Kubale: Interval vertex-coloring of a graph with forbidden colors. Disc. Math., 74, (1989), 125-136.
• [26] P. C. B. Lam, W. C. Shiu, C. S. Tong and C. F. Zhang: On the equitable chromatic number of complete n-partite graphs. Disc. Appl. Math., 113(2-3), (2001), 307-310.
• [27] K. W. Lih and P. L. Wu: On equitable coloring of bipartite graphs. Disc. Math., 151 (1996), 155-160.
• [28] W.-H. Lin and G. J. Chang: Equitable colorings of Kronecker products of graphs. Disc. Appl. Math., 158 (2010), 1816-1826.
• [29] W.-H. Lin and G. J. Chang: Equitable colorings of Cartesian products of graphs. Disc. Appl. Math., 160 (2012), 239-247.
• [30] W. Meyer: Equitable coloring. Amer. Math. Monthly, 80 (1973), 920-922. [31] K. Nakprasit: Equitable colorings of planar graphs with maximum degree at least nine. Disc. Math., 312 (2012), 1019-1024.
• [32] K. Nakprasit and K. Nakprasit: Equitable colorings of planar graphs without short cycles. Theoret. Comput. Sci., 465 (2012), 21-27.
• [33] W. Wang and K. Zhang: Equitable colorings of line graphs and complete r-partite graphs. Systems Science and Mathematical Sciences, 13(2), (2000), 190-194,
• [34] Z. D. Yan and W. Wang: Equitable chromatic threshold of Kronecker products of complete graphs. arXiv:1208.0918v3, 2012.
• [35] H. P. Yap and Y. Zhang: The equitable Δ-coloring conjecture holds for outerplanar graphs. Bulletin of the Inst. of Math. Academia Sinica, 25 (1997), 143-149.
• [36] H. P. Yap and Y. Zhang: Equitable colourings of planar graphs. J. Comb. Math. Comb. Comput., 27 (1998), 97-105.
• [37] J. Zhu and Y. Bu: Equitable list colorings of planar graphs without short cycles. Theoret. Comput. Sci., 407 (2008), 21-28.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę