A survey of graph coloring : its types, methods and applications

• Autorzy: Formanowicz P. , Tanaś K.
• Języki publikacji: EN

Abstrakty

EN

Graph coloring is one of the best known, popular and extensively researched subject in the field of graph theory, having many applications and conjectures, which are still open and studied by various mathematicians and computer scientists along the world. In this paper we present a survey of graph coloring as an important subfield of graph theory, describing various methods of the coloring, and a list of problems and conjectures associated with them. Lastly, we turn our attention to cubic graphs, a class of graphs, which has been found to be very interesting to study and color. A brief review of graph coloring methods (in Polish) was given by Kubale and a more detailed one in a book by the same author. We extend this review and explore the field of graph coloring further, describing various results obtained by other authors and show some interesting applications of this field of graph theory.

Słowa kluczowe

EN

graph coloring; vertex coloring; edge colouring; complexity; algorithms

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2012
• Tom: Vol. 37, No. 3
• Strony: 223--238
• Opis fizyczny: Bibliogr. 45 poz.

Twórcy

autor

Formanowicz P.

• Poznań University of Technology, Institute of Computing Science

autor

Tanaś K.

• Institute of Bioorganic Chemistry, Polish Academy of Sciences

Bibliografia

• [1] Chappell G. Hal A. Kundgen A. Ramamurthi R. Albertson, M.O. Coloring with no 2-colored p4's. Electronic Journal of Combinatorics, 11(1), 2004.
• [2] McDiarmid C. Reed B. Alon, N. Acyclic coloring of graphs. Random Structures and Algorithms, 2(3):277_288, 1991.
• [3] Sudakov B. Zaks A. Alon, N. Acyclic edge colorings of graphs. J. Graph Theory, 37(3):157_167, 2001.
• [4] Zaks A. Alon, N. Algorithmic aspects of acyclic edge colorings. Algorithmica, 32(4):611_614, 2002.
• [5] Haken W. Appel, K. Every planar graph is four-colorable. Illinois. J. Math., 21:429_490, 1976.
• [6] Courtney L. Baber. An introduction to list colorings of graphs. Master's thesis, Virginia Polytechnic Institute and State University, Blacksburg, Virginia, April 2009.
• [7] Hujter M. Tuza Z. Biro, M. Precoloring extensions. i. interval graphs. Discrete Mathematics, 100:267_279, 1992.
• [8] D. Brelaz. New methods to color the vertices of a graph. Comm. ACM, 22:251_ 256, 1979.
• [9] M.I. Burstein. Every 4-valent graph has an acyclic 5-coloring. Soobsc. Akad. Nauk Gruzin. SSR, 93:21_24, 1979.
• [10] Havet F. Muller T. Cohen, N. Acyclic edge-colouring of planar graphs. Technical report, Institut National de Recherche en Informatique et en Automatique, March 2009.
• [11] Grotschel M. Koster A. Eisenblatter, A. Frequency planning and rami_cations of coloring. Technical report, Konrad-Zuse-Zentrum fur Informationstechnik Berlin, Takustrasse 7, D-14196 Berlin-Dahlem, Germany, December 2000.
• [12] Rubin A.L. Taylor H. Erdos, P. Choosability in graphs. Congr. Numer., 26:125_ 157, 1979.
• [13] Jansen K. Erlebach, T. The complexity of path coloring and call scheduling. Theor. Comp. Sci, 255:33_50, 2001.
• [14] Raspaud Andre Fan, Genghua. Fulkerson's conjecture and circuit covers. J. Comb. Theory, Ser. B, 61(1):133_138, 1994.
• [15] Raspaud A. Reed B. Fertin, G. Star coloring of graphs. Journal of Graph Theory, 47(3):163_182, 2004.
• [16] Tana± K. Formanowicz, P. The Fan-Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks. Int. J. Appl. Math. Comput Sci., 22(3):765_778, 2012.
• [17] D.R. Fulkerson. Blocking and anti-blocking pairs of polyhedra. Math. Programming, 1:168_194, 1971.
• [18] Kubale M. Furma«czyk, H. The complexity of equitable vertex colorings of graphs. Journal of Applied Computer Science, 13(2):95_106, 2005.
• [19] Johnson D.S. Stockmeyer L. Garey, M.R. Some simpli_ed np-complete graph problems. Theor. Comp. Sci., 1:237_267, 1976.
• [20] B. Grunbaum. Acyclic coloring of planar graphs. Israel J. Math., 14(390-408), 1973.
• [21] Szemeredi E. Hajnal, A. Proof of a conjecture of p. Erdos. In Balatonfured Proc. Colloq., editor, Combinatorial theory and its applications, II, pages 601_ 623. North-Holland, 1970.
• [22] Drechsler N. Drechsler R. Hilgemeier, M. Fast heuristics for the edge coloring of large graphs. In Euromicro Symposium on Digital System Design, 2003. Proceedings., 2003.
• [23] I. Holyer. The np-completeness of edge colourings. SIAM J. Computing, 10:718_ 720, 1981.
• [24] T.E. Hu_man. Total coloring of graphs. Master's thesis, San Jose State University, 1989.
• [25] S. Isobe. Algorithms for the Total Colorings of Graphs. PhD thesis, Graduate School of Information Sciences, Tohoku University, Japan, February 2002.
• [26] Kuszner .. Mała_ejski M. Nadolski A. Janczewski, R. An approximate algorithm for circular edge coloring of graphs. Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej, 2:473_479, 2003.
• [27] Toft B. Jensen, T.R. Graph Coloring Problems. John Wiley and Sons, New York, 1995.
• [28] Toft B. Jensen, T.R. 25 pretty graph colouring problems. Discrete Mathematics, 229:167_169, February 2001.
• [29] Kostochka A.V. Mydlarz M. Szemeredi E. Kierstead, H.A. A fast algorithm for equitable coloring. Combinatorica, 30(2):217_224, 2010.
• [30] A.V. Kostochka. Upper bounds of chromatic functions of graphs. PhD thesis, Novosibirsk, 1978.
• [31] M. Kubale, editor. Contemporary Mathematics. Graph Colorings, volume 352, chapter 9, page 126. American mathematical Society, 2004.
• [32] M. Kubale. Modele i metody kolorowania grafów. Cz¦±¢ I (in Polish). Przegl¡d Elektrotechniczny (Electrical Review), 86:115_117, 2010.
• [33] A. Lyons. Acyclic and star colorings of cographs. Discrete Appl. Math., 159(16):1842_1850, 2011.
• [34] W. Meyer. Equitable coloring. American Mathematical Monthly, 80(8):920_922, 1973.
• [35] Thatcher J.W. Miller, R.E., editor. Complexity of Computer Computations, chapter Reducibility among combinatorial problems, pages 85_103. Plenum Press, New York, 1972.
• [36] Ghandehari M. Modarres, M. Applying circular coloring to open shop scheduling. Scientia Iranica, 15(5):652_660, October 2008.
• [37] Reed B. Molloy, M. A bound on the total chromatic number. Combinatorica, 18(2), 241-280 1998.
• [38] Zhou X. Nishizeki T. Nakano, S. Edge-coloring algorithms. Technical report, Graduate School of Information Sciences, Tohoku University, Sendai 980-77, Japan, 1996.
• [39] Tsouros C. Satratzemi, M. A heuristic algorithm for the list coloring of a random graph. In The 7th Balkan Conference on Operational Research, Constanta, Romania, 2005.
• [40] San Skulrattanakulchai. Acyclic colorings of subcubic graphs. Information processing letters, 92(4):161_167, 2004.
• [41] P.G. Tait. On the coloring of maps. Proc. Royal Soc. Edinburgh, 10:501_503, 1880.
• [42] A. Vince. Star chromatic number. Journal of Graph Theory, 12(4):551_559, 1988.
• [43] V.G. Vizing. On an estimate of the chromatic class of a p-graph. Diskret. Analiz., 3:24_30, 1964.
• [44] R.J.Waters. Graph Colouring and Frequency Assignment. PhD thesis, University of Nottingham, 2005.
• [45] Xuding Zhu. Circular chromatic number: a survey. Discrete Math., 229:371_410, 2001.