Skip to main content
Have a personal or library account? Click to login
A survey of graph coloring - its types, methods and applications Cover

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

Foundations of Computing and Decision Sciences
Volume 37 (2012): Issue 3 (September 2012)
By:  and    
Open Access
|Oct 2012
References

References

  1. [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.
    Open DOISearch in Google Scholar
  2. [2] McDiarmid C. Reed B. Alon, N. Acyclic coloring of graphs. Random Structures and Algorithms, 2(3):277_288, 1991.
    Open DOISearch in Google Scholar
  3. [3] Sudakov B. Zaks A. Alon, N. Acyclic edge colorings of graphs. J. Graph Theory, 37(3):157_167, 2001.
    Open DOISearch in Google Scholar
  4. [4] Zaks A. Alon, N. Algorithmic aspects of acyclic edge colorings. Algorithmica, 32(4):611_614, 2002.
    Open DOISearch in Google Scholar
  5. [5] Haken W. Appel, K. Every planar graph is four-colorable. Illinois. J. Math., 21:429_490, 1976.
    Open DOISearch in Google Scholar
  6. [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. [7] Hujter M. Tuza Z. Biro, M. Precoloring extensions. i. interval graphs. Discrete Mathematics, 100:267_279, 1992.
    Open DOISearch in Google Scholar
  8. [8] D. Brelaz. New methods to color the vertices of a graph. Comm. ACM, 22:251_ 256, 1979.
    Open DOISearch in Google Scholar
  9. [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. [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. [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. [12] Rubin A.L. Taylor H. Erdos, P. Choosability in graphs. Congr. Numer., 26:125_ 157, 1979.
    Search in Google Scholar
  13. [13] Jansen K. Erlebach, T. The complexity of path coloring and call scheduling. Theor. Comp. Sci, 255:33_50, 2001.
    Open DOISearch in Google Scholar
  14. [14] Raspaud Andre Fan, Genghua. Fulkerson's conjecture and circuit covers. J. Comb. Theory, Ser. B, 61(1):133_138, 1994.
    Open DOISearch in Google Scholar
  15. [15] Raspaud A. Reed B. Fertin, G. Star coloring of graphs. Journal of Graph Theory, 47(3):163_182, 2004.
    Open DOISearch in Google Scholar
  16. [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. [17] D.R. Fulkerson. Blocking and anti-blocking pairs of polyhedra. Math. Programming, 1:168_194, 1971.
    Open DOISearch in Google Scholar
  18. [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. [19] Johnson D.S. Stockmeyer L. Garey, M.R. Some simpli_ed np-complete graph problems. Theor. Comp. Sci., 1:237_267, 1976.
    Open DOISearch in Google Scholar
  20. [20] B. Grunbaum. Acyclic coloring of planar graphs. Israel J. Math., 14(390-408), 1973.
    Open DOISearch in Google Scholar
  21. [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. [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. [23] I. Holyer. The np-completeness of edge colourings. SIAM J. Computing, 10:718_ 720, 1981.
    Open DOISearch in Google Scholar
  24. [24] T.E. Hu_man. Total coloring of graphs. Master's thesis, San Jose State University, 1989.
    Search in Google Scholar
  25. [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. [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. [27] Toft B. Jensen, T.R. Graph Coloring Problems. John Wiley and Sons, New York, 1995.
    Open DOISearch in Google Scholar
  28. [28] Toft B. Jensen, T.R. 25 pretty graph colouring problems. Discrete Mathematics, 229:167_169, February 2001.
    Open DOISearch in Google Scholar
  29. [29] Kostochka A.V. Mydlarz M. Szemeredi E. Kierstead, H.A. A fast algorithm for equitable coloring. Combinatorica, 30(2):217_224, 2010.
    Open DOISearch in Google Scholar
  30. [30] A.V. Kostochka. Upper bounds of chromatic functions of graphs. PhD thesis, Novosibirsk, 1978.
    Search in Google Scholar
  31. [31] M. Kubale, editor. Contemporary Mathematics. Graph Colorings, volume 352, chapter 9, page 126. American mathematical Society, 2004.
    Open DOISearch in Google Scholar
  32. [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. [33] A. Lyons. Acyclic and star colorings of cographs. Discrete Appl. Math., 159(16):1842_1850, 2011.
    Open DOISearch in Google Scholar
  34. [34] W. Meyer. Equitable coloring. American Mathematical Monthly, 80(8):920_922, 1973.
    Open DOISearch in Google Scholar
  35. [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.
    Open DOISearch in Google Scholar
  36. [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. [37] Reed B. Molloy, M. A bound on the total chromatic number. Combinatorica, 18(2), 241-280 1998.
    Open DOISearch in Google Scholar
  38. [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. [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. [40] San Skulrattanakulchai. Acyclic colorings of subcubic graphs. Information processing letters, 92(4):161_167, 2004.
    Open DOISearch in Google Scholar
  41. [41] P.G. Tait. On the coloring of maps. Proc. Royal Soc. Edinburgh, 10:501_503, 1880.
    Open DOISearch in Google Scholar
  42. [42] A. Vince. Star chromatic number. Journal of Graph Theory, 12(4):551_559, 1988.
    Open DOISearch in Google Scholar
  43. [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. [44] R.J.Waters. Graph Colouring and Frequency Assignment. PhD thesis, University of Nottingham, 2005.
    Search in Google Scholar
  45. [45] Xuding Zhu. Circular chromatic number: a survey. Discrete Math., 229:371_410, 2001.
    Search in Google Scholar
DOI: https://doi.org/10.2478/v10209-011-0012-y | Journal eISSN: 2300-3405 (formerly 0867-6356) | Journal ISSN: 0867-6356
Journal RSS Feed
Language: English
Page range: 223 - 238
Published on: Oct 1, 2012
Published by: Poznan University of Technology
In partnership with: Paradigm Publishing Services
Keywords:
graph coloring,
vertex coloring,
edge coloring,
complexity,
algorithms
Related subjects:
Computer sciences,
Software development

© 2012 Piotr Formanowicz, Krzysztof Tanaś, published by Poznan University of Technology
This work is licensed under the Creative Commons License.

Volume 37 (2012): Issue 3 (September 2012)
Previous article