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

[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.10.37236/1779Search in Google Scholar

[2] McDiarmid C. Reed B. Alon, N. Acyclic coloring of graphs. Random Structures and Algorithms, 2(3):277_288, 1991.10.1002/rsa.3240020303Search in Google Scholar

[3] Sudakov B. Zaks A. Alon, N. Acyclic edge colorings of graphs. J. Graph Theory, 37(3):157_167, 2001.10.1002/jgt.1010Search in Google Scholar

[4] Zaks A. Alon, N. Algorithmic aspects of acyclic edge colorings. Algorithmica, 32(4):611_614, 2002.10.1007/s00453-001-0093-8Search in Google Scholar

[5] Haken W. Appel, K. Every planar graph is four-colorable. Illinois. J. Math., 21:429_490, 1976.10.1215/ijm/1256049011Search in Google Scholar

[6] Courtney L. Baber. An introduction to list colorings of graphs. Master's thesis, Virginia Polytechnic Institute and State University, Blacksburg, Virginia, April 2009.Search in Google Scholar

[7] Hujter M. Tuza Z. Biro, M. Precoloring extensions. i. interval graphs. Discrete Mathematics, 100:267_279, 1992.10.1016/0012-365X(92)90646-WSearch in Google Scholar

[8] D. Brelaz. New methods to color the vertices of a graph. Comm. ACM, 22:251_ 256, 1979.10.1145/359094.359101Search in Google Scholar

[9] M.I. Burstein. Every 4-valent graph has an acyclic 5-coloring. Soobsc. Akad. Nauk Gruzin. SSR, 93:21_24, 1979.Search in Google Scholar

[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.Search in Google Scholar

[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.Search in Google Scholar

[12] Rubin A.L. Taylor H. Erdos, P. Choosability in graphs. Congr. Numer., 26:125_ 157, 1979.Search in Google Scholar

[13] Jansen K. Erlebach, T. The complexity of path coloring and call scheduling. Theor. Comp. Sci, 255:33_50, 2001.10.1016/S0304-3975(99)00152-8Search in Google Scholar

[14] Raspaud Andre Fan, Genghua. Fulkerson's conjecture and circuit covers. J. Comb. Theory, Ser. B, 61(1):133_138, 1994.10.1006/jctb.1994.1039Search in Google Scholar

[15] Raspaud A. Reed B. Fertin, G. Star coloring of graphs. Journal of Graph Theory, 47(3):163_182, 2004.10.1002/jgt.20029Search in Google Scholar

[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.Search in Google Scholar

[17] D.R. Fulkerson. Blocking and anti-blocking pairs of polyhedra. Math. Programming, 1:168_194, 1971.10.1007/BF01584085Search in Google Scholar

[18] Kubale M. Furma«czyk, H. The complexity of equitable vertex colorings of graphs. Journal of Applied Computer Science, 13(2):95_106, 2005.Search in Google Scholar

[19] Johnson D.S. Stockmeyer L. Garey, M.R. Some simpli_ed np-complete graph problems. Theor. Comp. Sci., 1:237_267, 1976.10.1016/0304-3975(76)90059-1Search in Google Scholar

[20] B. Grunbaum. Acyclic coloring of planar graphs. Israel J. Math., 14(390-408), 1973.10.1007/BF02764716Search in Google Scholar

[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.Search in Google Scholar

[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.Search in Google Scholar

[23] I. Holyer. The np-completeness of edge colourings. SIAM J. Computing, 10:718_ 720, 1981.10.1137/0210055Search in Google Scholar

[24] T.E. Hu_man. Total coloring of graphs. Master's thesis, San Jose State University, 1989.Search in Google Scholar

[25] S. Isobe. Algorithms for the Total Colorings of Graphs. PhD thesis, Graduate School of Information Sciences, Tohoku University, Japan, February 2002.Search in Google Scholar

[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.Search in Google Scholar

[27] Toft B. Jensen, T.R. Graph Coloring Problems. John Wiley and Sons, New York, 1995.10.1002/9781118032497Search in Google Scholar

[28] Toft B. Jensen, T.R. 25 pretty graph colouring problems. Discrete Mathematics, 229:167_169, February 2001.10.1016/S0012-365X(00)00206-5Search in Google Scholar

[29] Kostochka A.V. Mydlarz M. Szemeredi E. Kierstead, H.A. A fast algorithm for equitable coloring. Combinatorica, 30(2):217_224, 2010.10.1007/s00493-010-2483-5Search in Google Scholar

[30] A.V. Kostochka. Upper bounds of chromatic functions of graphs. PhD thesis, Novosibirsk, 1978.Search in Google Scholar

[31] M. Kubale, editor. Contemporary Mathematics. Graph Colorings, volume 352, chapter 9, page 126. American mathematical Society, 2004.10.1090/conm/352Search in Google Scholar

[32] M. Kubale. Modele i metody kolorowania grafów. Cz¦±¢ I (in Polish). Przegl¡d Elektrotechniczny (Electrical Review), 86:115_117, 2010.Search in Google Scholar

[33] A. Lyons. Acyclic and star colorings of cographs. Discrete Appl. Math., 159(16):1842_1850, 2011.10.1016/j.dam.2011.04.011Search in Google Scholar

[34] W. Meyer. Equitable coloring. American Mathematical Monthly, 80(8):920_922, 1973.10.1080/00029890.1973.11993408Search in Google Scholar

[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.10.1007/978-1-4684-2001-2_9Search in Google Scholar

[36] Ghandehari M. Modarres, M. Applying circular coloring to open shop scheduling. Scientia Iranica, 15(5):652_660, October 2008.Search in Google Scholar

[37] Reed B. Molloy, M. A bound on the total chromatic number. Combinatorica, 18(2), 241-280 1998.10.1007/PL00009820Search in Google Scholar

[38] Zhou X. Nishizeki T. Nakano, S. Edge-coloring algorithms. Technical report, Graduate School of Information Sciences, Tohoku University, Sendai 980-77, Japan, 1996.Search in Google Scholar

[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.Search in Google Scholar

[40] San Skulrattanakulchai. Acyclic colorings of subcubic graphs. Information processing letters, 92(4):161_167, 2004.10.1016/j.ipl.2004.08.002Search in Google Scholar

[41] P.G. Tait. On the coloring of maps. Proc. Royal Soc. Edinburgh, 10:501_503, 1880.10.1017/S0370164600044229Search in Google Scholar

[42] A. Vince. Star chromatic number. Journal of Graph Theory, 12(4):551_559, 1988.10.1002/jgt.3190120411Search in Google Scholar

[43] V.G. Vizing. On an estimate of the chromatic class of a p-graph. Diskret. Analiz., 3:24_30, 1964.Search in Google Scholar

[44] R.J.Waters. Graph Colouring and Frequency Assignment. PhD thesis, University of Nottingham, 2005.Search in Google Scholar

[45] Xuding Zhu. Circular chromatic number: a survey. Discrete Math., 229:371_410, 2001. Search in Google Scholar