Graph colorings with local constraints - a survey

Zsolt Tuza

Discussiones Mathematicae Graph Theory (1997)

  • Volume: 17, Issue: 2, page 161-228
  • ISSN: 2083-5892

Abstract

top
We survey the literature on those variants of the chromatic number problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the list colorings and the precoloring extensions are considered. In one of the most general formulations, a graph G = (V,E), sets L(v) of admissible colors, and natural numbers c v for the vertices v ∈ V are given, and the question is whether there can be chosen a subset C(v) ⊆ L(v) of cardinality c v for each vertex in such a way that the sets C(v),C(v’) are disjoint for each pair v,v’ of adjacent vertices. The particular case of constant |L(v)| with c v = 1 for all v ∈ V leads to the concept of choice number, a graph parameter showing unexpectedly different behavior compared to the chromatic number, despite these two invariants have nearly the same value for almost all graphs. To illustrate typical techniques, some of the proofs are sketched.

How to cite

top

Zsolt Tuza. "Graph colorings with local constraints - a survey." Discussiones Mathematicae Graph Theory 17.2 (1997): 161-228. <http://eudml.org/doc/270527>.

@article{ZsoltTuza1997,
abstract = {We survey the literature on those variants of the chromatic number problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the list colorings and the precoloring extensions are considered. In one of the most general formulations, a graph G = (V,E), sets L(v) of admissible colors, and natural numbers $c_v$ for the vertices v ∈ V are given, and the question is whether there can be chosen a subset C(v) ⊆ L(v) of cardinality $c_v$ for each vertex in such a way that the sets C(v),C(v’) are disjoint for each pair v,v’ of adjacent vertices. The particular case of constant |L(v)| with $c_v$ = 1 for all v ∈ V leads to the concept of choice number, a graph parameter showing unexpectedly different behavior compared to the chromatic number, despite these two invariants have nearly the same value for almost all graphs. To illustrate typical techniques, some of the proofs are sketched.},
author = {Zsolt Tuza},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph coloring; list coloring; choice number; precoloring extension; complexity of algorithms; chromatic number; list colorings; precoloring extensions; complexity},
language = {eng},
number = {2},
pages = {161-228},
title = {Graph colorings with local constraints - a survey},
url = {http://eudml.org/doc/270527},
volume = {17},
year = {1997},
}

TY - JOUR
AU - Zsolt Tuza
TI - Graph colorings with local constraints - a survey
JO - Discussiones Mathematicae Graph Theory
PY - 1997
VL - 17
IS - 2
SP - 161
EP - 228
AB - We survey the literature on those variants of the chromatic number problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the list colorings and the precoloring extensions are considered. In one of the most general formulations, a graph G = (V,E), sets L(v) of admissible colors, and natural numbers $c_v$ for the vertices v ∈ V are given, and the question is whether there can be chosen a subset C(v) ⊆ L(v) of cardinality $c_v$ for each vertex in such a way that the sets C(v),C(v’) are disjoint for each pair v,v’ of adjacent vertices. The particular case of constant |L(v)| with $c_v$ = 1 for all v ∈ V leads to the concept of choice number, a graph parameter showing unexpectedly different behavior compared to the chromatic number, despite these two invariants have nearly the same value for almost all graphs. To illustrate typical techniques, some of the proofs are sketched.
LA - eng
KW - graph coloring; list coloring; choice number; precoloring extension; complexity of algorithms; chromatic number; list colorings; precoloring extensions; complexity
UR - http://eudml.org/doc/270527
ER -

References

top
  1. [1] M. Ajtai, J. Komlós, E. Szemerédi, A note on Ramsey numbers, Journal of Combinatorial Theory, Ser. A 29 (1980) 354-360. Zbl0455.05045
  2. [2] M.O. Albertson, You can't paint yourself into a corner, Manuscript, 1997. 
  3. [3] N. Alon, Choice numbers of graphs : A probabilistic approach, Combinatorics, Probability and Computing 1 (1992) 107-114, doi:10.1017/S0963548300000122. 
  4. [4] N. Alon, Restricted colorings of graphs, Surveys in Combinatorics (K. Walker, ed.), Proc. 14th British Combinatorial Conference, London Math. Soc. Lecture Notes Series 187, Cambridge University Press, 1993, 1-33. Zbl0791.05034
  5. [5] N. Alon, Private communication, October 1995. 
  6. [6] N. Alon, K. Berman, Regular hypergraphs, Gordon's lemma, Steinitz's lemma and Invariant Theory, Journal of Combinatorial Theory, Ser. A 43 (1986) 91-97. Zbl0611.05044
  7. [7] N. Alon, M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992) 125-134, doi: 10.1007/BF01204715. Zbl0756.05049
  8. [8] N. Alon, Zs. Tuza, M. Voigt, Choosability and fractional chromatic numbers, Discrete Mathematics 165/166 (1997) 31-38, doi: 10.1016/S0012-365X(96)00159-8. Zbl0877.05020
  9. [9] N. Alon, A. Zaks, T-choosability in graphs, Manuscript, 1996. 
  10. [10] L.D. Andersen, Completing partial latin squares, Mat. Fys. Medd. Danske Vid. Selsk. 41 (1985) 23-69. 
  11. [11] L.D. Andersen, A.J.W. Hilton, Symmetric Latin Square and Complete Graph Analogues of the Evans Conjecture, Journal of Combinatorial Designs 2 (1994) 197-252, doi: 10.1002/jcd.3180020404. Zbl0821.05005
  12. [12] S. Arnborg, A. Proskurowski, Linear-time algorithms for NP-hard problems on graphs embedded in k-trees, Discrete Applied Mathematics 23 (1989) 11-24, doi: 10.1016/0166-218X(89)90031-0. Zbl0666.68067
  13. [13] E. Arroyo, Thesis, Kennesaw State University, GA, in preparation. 
  14. [14] J. Beck, On 3-chromatic hypergraphs, Discrete Mathematics 24 (1978) 127-137, doi: 10.1016/0012-365X(78)90191-7. Zbl0429.05055
  15. [15] C. Berge, Graphs. North-Holland, 1985. 
  16. [16] E.R. Berlekamp, J.H. Conway, R.K. Guy, Winning Ways for your Mathematical Plays. Academic Press, 1982. Zbl0485.00025
  17. [17] M. Biró, M. Hujter, Zs. Tuza, Precoloring extension, Technical Report, Computer and Automation Institute, Budapest, 1990. 
  18. [18] M. Biró, M. Hujter, Zs. Tuza, Precoloring extension, I. Interval graphs, Discrete Mathematics 100 (1992) 267-279, doi: 10.1016/0012-365X(92)90646-W. 
  19. [19] M. Biró, M. Hujter, Zs. Tuza, Cross fertilisation of graph theory and aircraft maintenance scheduling, Thirty-Second Annual Symposium (G. Davison, ed.), AGIFORS (Airline Group of the International Federation of Operational Research Societies), 1993, 307-317. 
  20. [20] H.L. Bodlaender, On the complexity of some coloring games, 2 : 2 (1991) 133-147. Zbl0753.05061
  21. [21] H. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Müller, Zs. Tuza, Rankings of graphs, Graph Theoretic Concepts in Computer Science (E. W. Mayr et al., eds.), Lecture Notes in Computer Science 903, Springer-Verlag, 1995, 292-304. 
  22. [22] H.L. Bodlaender, K. Jansen, G.J. Woeginger, Scheduling with incompatible jobs, Discrete Applied Mathematics 55 (1994) 219-232, doi: 10.1016/0166-218X(94)90009-4. Zbl0822.68011
  23. [23] H.L. Bodlaender, D. Kratsch, The complexity of coloring games on perfect graphs, Theoretical Computer Science 106 (1992) 309-326, doi: 10.1016/0304-3975(92)90254-D. Zbl0785.90119
  24. [24] B. Bollobás, Chromatic number, girth and maximal degree, Discrete Mathematics 24 (1978) 311-314, doi: 10.1016/0012-365X(78)90102-4. Zbl0395.05034
  25. [25] B. Bollobás, The chromatic number of random graphs, Combinatorica 8 (1988) 49-55, doi: 10.1007/BF02122551. Zbl0666.05033
  26. [26] B. Bollobás, A.J. Harris, List-colourings of graphs, Graphs and Combinatorics 1 (1985) 115-127, doi: 10.1007/BF02582936. Zbl0606.05027
  27. [27] B. Bollobás, H.R. Hind, A new upper bound for the list chromatic number, Discrete Mathematics 74 (1989) 65-75, doi: 10.1016/0012-365X(89)90199-4. Zbl0674.05027
  28. [28 ] J.A. Bondy, R. Boppana, A. Siegel, Unpublished, 1989. 
  29. [29] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications. Elsevier, New York, 1976. Zbl1226.05083
  30. [30] O.V. Borodin, Problems of coloring and covering the vertex set of a graph by induced subgraphs. Ph.D. Thesis, Novosibirsk, USSR, 1979 (in Russian). Announced in: Criterion of chromaticity of a degree prescription, Abstracts of IV. All-Union Conf. on Theoretical Cybernetics, Novosibirsk, 1977, 127-128. 
  31. [31] O.V. Borodin, On the total coloring of planar graphs, J. Reine Angew. Math. 394 (1989) 180-185, doi: 10.1515/crll.1989.394.180. Zbl0653.05029
  32. [32] O.V. Borodin, A.V. Kostochka, D.R. Woodall, List edge and list total colourings of multigraphs, Journal of Combinatorial Theory, Ser. B, in print. Zbl0876.05032
  33. [33] M. Borowiecki, I. Broere, M. Frick, P. Mihók, G. Semanišin, Survey of hereditary properties of graphs, Discussiones Mathematicae - Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. Zbl0902.05026
  34. [34] M. Borowiecki, I. Broere, P. Mihók, On generalized list colourings of graphs, Discussiones Mathematicae - Graph Theory 17 (1997) 127-132, doi: 10.7151/dmgt.1045. Zbl0903.05022
  35. [35] M. Borowiecki, E. Drgas-Burchardt, P. Mihók, Generalized list colourings of graphs, Discussiones Mathematicae - Graph Theory 15 (1995) 185-193, doi: 10.7151/dmgt.1016. Zbl0845.05046
  36. [36] M. Borowiecki, P. Mihók, Hereditary properties of graphs, Advances in Graph Theory (V.R. Kulli, ed.), Vishwa International Publications, Gulbarga, 1991, 41-68. 
  37. [37] D.P. Bovet, P. Crescenzi, Introduction to the Theory of Complexity. Prentice Hall International Series in Computer Science, 1994. Zbl0809.68067
  38. [38] R.L. Brooks, On colouring the nodes of a network, Proceedings of the Cambridge Philos. Soc. 37 (1941) 194-197, doi: 10.1017/S030500410002168X. Zbl0027.26403
  39. [39] J.I. Brown, D. Kelly, J. Schönheim, R.E. Woodrow, Graph coloring satisfying restraints, Discrete Mathematics 80 (1990) 123-143, doi: 10.1016/0012-365X(90)90113-V. Zbl0696.05024
  40. [40] S.A. Burr, Some undecidable problems involving the edge-coloring and vertex-coloring of graphs, Discrete Mathematics 50 (1984) 171-177, doi: 10.1016/0012-365X(84)90046-3. Zbl0553.05053
  41. [41] A.G. Chetwynd, R. Häggkvist, A note on list-colorings, Journal of Graph Theory 13 (1989) 87-95, doi: 10.1002/jgt.3190130112. Zbl0674.05026
  42. [42] C.J. Colbourn, The complexity of completing partial Latin squares, Annals of Discrete Mathematics 8 (1984) 25-30, doi: 10.1016/0166-218X(84)90075-1. Zbl0538.05013
  43. [43] D.G. Cornell, Y. Perl, L.K. Stewart, A linear recognition algorithm for cographs, SIAM Journal on Computing 4 (1985) 926-934, doi: 10.1137/0214065. Zbl0575.68065
  44. [44] B. Courcelle, The monadic second-order logic of graphs, I : Recognizable sets of finite graphs, Information and Computation 85 (1990) 12-75, doi: 10.1016/0890-5401(90)90043-H. Zbl0722.03008
  45. [45] L.J. Cowen, R.H. Cowen, D.R. Woodall, Defective colorings of graphs in surfaces ; partitions into subgraphs of bounded valency, Journal of Graph Theory 10 (1986) 187-195, doi: 10.1002/jgt.3190100207. Zbl0596.05024
  46. [46] D. de Werra, Restricted models for timetabling, Discrete Mathematics 165/166 (1997) 161-170, doi: 10.1016/S0012-365X(96)00208-7. Zbl0876.90060
  47. [47] D. de Werra, The combinatorics of timetabling, 96 (1997) 504-513. Zbl0917.90190
  48. [48] D. de Werra, Mathematical programming models in chromatic scheduling, Manuscript, 1997. 
  49. [49] J.H. Dinitz, W.J. Martin, The stipulation polynomial of a uniquely list-colorable graph, Australasian Journal of Combinatorics 11 (1995) 105-115. Zbl0826.05025
  50. [50] Q. Donner, On the number of list-colorings, Journal of Graph Theory 16 (1992) 239-245, doi: 10.1002/jgt.3190160307. Zbl0754.05038
  51. [51] M. Dror, G. Finke, S. Gravier, W. Kubiak, On the complexity of a restricted list-coloring problem, Manuscript, 1997. Zbl0928.05057
  52. [52] D.Z. Du, D.F. Hsu, F.K. Hwang, The Hamiltonian property of consecutive-d digraphs, 17 : 11 (1993) 61-63. Zbl0789.05040
  53. [53] P. Dukes, H. Emerson, G. MacGillivray, Undecidable generalized colouring problems, Journal of Combinatorial Mathematics and Combinatorial Computing, to appear. Zbl0897.05039
  54. [54] N. Eaton, Unpublished, 1996. 
  55. [55] N. Eaton, T. Hull, Private communication, June 1997. 
  56. [56] J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices, 69 (1965) 125-130. 
  57. [57] J. Edmonds, D.R. Fulkerson, Transversals and matroid partition, 69 (1965) 147-153. Zbl0141.21801
  58. [58] M.N. Ellingham, L. Goddyn, List edge colourings of some 1-factorizable multigraphs, Combinatorica 16 (1996) 343-352, doi: 10.1007/BF01261320. Zbl0860.05035
  59. [59] P. Erdős, On a combinatorial problem, II, Acta Math. Acad. Sci. Hungar. 15 (1964) 445-447, doi: 10.1007/BF01897152. 
  60. [60] P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981) 25-42, doi: 10.1007/BF02579174. Zbl0486.05001
  61. [61] P. Erdős, L. Lovász, Problems and results on 3-chromatic hypergraphs and related questions, Infinite and Finite Sets (A. Hajnal, L. Lovász and V. Sós, eds.), Colloq. Math. Soc. J. Bolyai, 10, North-Holland, Amsterdam, 1974, 609-627. 
  62. [62] P. Erdős, A.L. Rubin, H. Taylor, Choosability in graphs, Proc. West-Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, California, Congressus Numerantium XXVI (1979) 125-157. 
  63. [63] S. Even, A. Itai, A. Shamir, On the complexity of time table and multicommodity flow problems, SIAM Journal on Computing 5 (1976) 691-703, doi: 10.1137/0205048. Zbl0358.90021
  64. [64] U. Faigle, U. Kern, H. Kierstead, W.T. Trotter, On the game chromatic number of some classes of graphs, Ars Combinatoria 35 (1993) 143-150. Zbl0796.90082
  65. [65] M. Farber, M. Hujter, Zs. Tuza, An upper bound on the number of cliques in a graph, Networks 23 (1993) 207-210, doi: 10.1002/net.3230230308. 
  66. [66] A.S. Finbow, B.L. Hartnell, A game related to covering by stars, Ars Combinatoria 16-A (1983) 189-198. Zbl0559.90095
  67. [67] H. Fleischner, M. Stiebitz, A solution to a colouring problem of P. Erdős, Discrete Mathematics 101 (1992) 39-48, doi: 10.1016/0012-365X(92)90588-7. 
  68. [68] D. Gale, S. Shapley, College admissions and the stability of marriage, American Mathematical Monthly 69 (1962) 9-15, doi: 10.2307/2312726. Zbl0109.24403
  69. [69] T. Gallai, Kritische Graphen I, II, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963) 165-192 ; 373-395. 
  70. [70] F. Galvin, The list chromatic index of a bipartite multigraph, Journal of Combinatorial Theory, Ser. B 63 (1995) 153-158. Zbl0826.05026
  71. [71] M.R. Garey, D.S. Johnson, Computers and Intractability - A Guide to the Theory of NP-Completeness. Freeman, New York, 1979. Zbl0411.68039
  72. [72] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980. 
  73. [73] J.E. Graver, A survey of the maximum depth problem for indecomposable exact covers, Infinite and Finite Sets, Colloq. Math. Soc. János Bolyai, 1973, North-Holland, 731-743. 
  74. [74] S. Gravier, A Hajós-like theorem for list coloring, Discrete Mathematics 152 (1996) 299-302, doi: 10.1016/0012-365X(95)00350-6. Zbl0853.05037
  75. [75] S. Gravier, F. Maffray, On the choice number of 3-colorable elementary graphs, Discrete Mathematics 165/166 (1997) 353-358, doi: 10.1016/S0012-365X(96)00182-3. Zbl0888.05027
  76. [76] S. Gravier, F. Maffray, Graphs whose choice number is equal to their chromatic number, Manuscript, LSD2-IMAG, Grenoble, France, January 1995. Zbl0891.05031
  77. [77] H. Gröflin, Feasible graph coloring and a generalization of perfect graphs, Manuscript, University of Fribourg, 1992. 
  78. [78] M. Grötschel, L. Lovász, A. Schrijver, Polynomial algorithms for perfect graphs, Annals of Discrete Mathematics 21 (1984) 325-356. Zbl0554.05041
  79. [79] M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin, Heidelberg, 1988. Zbl0634.05001
  80. [80] R.P. Gupta, The chromatic index and the degree of a graph, Notices of the American Mathematical Society 13 (1966) Abstract 66T-429. 
  81. [81] S. Gutner, Choice Numbers of Graphs. M.Sc. Thesis, Tel Aviv University, 1992. 
  82. [82] S. Gutner, The complexity of planar graph choosability, Manuscript, 1994, to appear in Discrete Mathematics. Zbl0865.05066
  83. [83] S. Gutner, M. Tarsi, Some results on (a:b)-choosability, To appear. Zbl1198.05049
  84. [94] R. Häggkvist, Towards a solution of the Dinitz problem ? Discrete Mathematics 75 (1989) 247-251. Zbl0669.05014
  85. [85] R. Häggkvist, Restricted edge-colourings of bipartite graphs, Combinatorics, Probability and Computing 5 (1996) 385-392, doi: 10.1017/S0963548300002133. Zbl0863.05039
  86. [86] R. Häggkvist, A. Chetwynd, Some upper bounds on the total and list chromatic numbers of multigraphs, Journal of Graph Theory 16 (1992) 503-516, doi: 10.1002/jgt.3190160510. Zbl0814.05038
  87. [87] R. Häggkvist, J. Janssen, New bounds on the list-chromatic index of the complete graph and other simple graphs, Combinatorics, Probability and Computing (1997) in print. Zbl0880.05035
  88. [88] Gy. Hajós, Über eine Konstruktion nicht n-färbbarer Graphen, Wiss. Z. Martin Luther Univ. Math.-Natur. Reihe 10 (1961) 116-117. 
  89. [89] W.K. Hale, Frequency assignment : theory and applications, Proceedings of IEEE 68 (1980) 1497-1514, doi: 10.1109/PROC.1980.11899. 
  90. [90] D. Hanson, G. MacGillivray, B. Toft, Choosability of bipartite graphs, Ars Combinatoria 44 (1996) 183-192. Zbl0889.05048
  91. [91] F. Harary, Graph Theory. Addison-Wesley, 1969. 
  92. [92] F. Harary, Zs. Tuza, Two graph-colouring games, Bulletin of the Australian Mathematical Society 48 (1993) 141-149, doi: 10.1017/S0004972700015549. 
  93. [93] A. Hertz, Slim graphs, Graphs and Combinatorics 5 (1989) 149-157, doi: 10.1007/BF01788666. Zbl0677.05065
  94. [94] A.J.W. Hilton, P.D. Johnson, Jr., Extending Hall's theorem, Topics in Combinatorics and Graph Theory - Essays in Honour of Gerhard Ringel (R. Bodendiek et al., eds.), Teubner, 1990, 359-371. 
  95. [95] A.J.W. Hilton, P.D. Johnson, Jr., The Hall number, the Hall index, and the total Hall number of a graph, Manuscript, February 1997. Zbl0934.05001
  96. [96] A.J.W. Hilton, P.D. Johnson, Jr., E.B. Wantland, The Hall number of a simple graph, Congressus Numerantium, to appear. 
  97. [97] H.R. Hind, Restricted Edge-Colourings. Ph.D. Thesis, Peterhouse College, Cambridge, 1988. 
  98. [98] D.G. Hoffman, P.D. Johnson, Jr., On the choice number of K m , n , Congressus Numerantium 98 (1993) 105-111. Zbl0801.05027
  99. [99] D.G. Hoffman, P.D. Johnson, Jr., E.B. Wantland, Restricted choice numbers, Congressus Numerantium 105 (1994) 65-79. 
  100. [100] I. Holyer, The NP-completeness of edge-coloring, SIAM Journal on Computing 10 (1981) 718-720, doi: 10.1137/0210055. Zbl0473.68034
  101. [101] J. Hopcroft, R.M. Karp, An n 5 / 2 algorithm for maximum matching in bipartite graphs, SIAM Journal on Computing 2 (1973) 225-231, doi: 10.1137/0202019. Zbl0266.05114
  102. [102] R. Huang, G.-C. Rota, On the relations of various conjectures on Latin squares and straightening coefficients, Discrete Mathematics 128 (1994) 225-236, doi: 10.1016/0012-365X(94)90114-7. Zbl0797.05019
  103. [103] M. Hujter, Zs. Tuza, Precoloring extension, II. Graph classes related to bipartite graphs, Acta Mathematica Universitatis Comenianae 62 (1993) 1-11. 
  104. [104] M. Hujter, Zs. Tuza, The number of maximal independent sets in triangle-free graphs, SIAM Journal on Discrete Mathematics 6 (1993) 284-288, doi: 10.1137/0406022. Zbl0779.05025
  105. [105] M. Hujter, Zs. Tuza, Precoloring extension, III. Classes of perfect graphs, Combinatorics, Probability and Computing 5 (1996) 35-56, doi: 10.1017/S0963548300001826. Zbl0846.05034
  106. [106] M. Hujter, Zs. Tuza, Precoloring extension, IV. General bounds and list colorings, In preparation. 
  107. [107] F. Jaeger, On the Penrose number of cubic diagrams, Discrete Mathematics 74 (1989) 85-97, doi: 10.1016/0012-365X(89)90201-X. Zbl0679.05029
  108. [108] K. Jansen, The optimum cost chromatic partition problem, Algorithms and Complexity, Proc. CIAC 3 (G. Bongiovanni et al., eds.), Lecture Notes in Computer Science 1203 (1997) 25-36. Extended version : Complexity results for the optimum cost chromatic partition problem, Manuscript, 1997. 
  109. [109] K. Jansen, P. Scheffler, Generalized colorings for tree-like graphs, Discrete Applied Mathematics 75 (1997) 135-155. Preliminary version in : Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'92 (E. W. Mayr, ed.), Lecture Notes in Computer Science 657, Springer-Verlag, 1993, 50-59. 
  110. [110] J.C.M. Janssen, The Dinitz problem solved for rectangles, Bulletin of the American Mathematical Society 29 (1993) 243-249, doi: 10.1090/S0273-0979-1993-00430-0. Zbl0792.05053
  111. [111] T.R. Jensen, B. Toft, Graph Coloring Problems. Wiley Interscience, 1995. 
  112. [112] T.R. Jensen, B. Toft, Choosability versus chromaticity - the plane unit distance graph has a 2-chromatic subgraph of infinite list-chromatic number, Geombinatorics 5 (1995) 45-64. Zbl0855.05055
  113. [113] A. Johansson, An improved upper bound on the choice number for triangle free graphs, Manuscript, January 1996. 
  114. [114] A. Johansson, The choice number of sparse graphs, Preliminary version, April 1996. 
  115. [115] D.S. Johnson, M. Yannakakis, C.M. Papadimitriou, On generating all maximal independent sets, Information Processing Letters 27 (1988) 119-123, doi: 10.1016/0020-0190(88)90065-8. Zbl0654.68086
  116. [116] P.D. Johnson, Jr., The choice number of the plane, Geombinatorics 3 (1994) 122-128. Zbl0848.05031
  117. [117] M. Juvan, B. Mohar, List colorings of outerplanar graphs, Manuscript, 1996. 
  118. [118] M. Juvan, B. Mohar, R. Skrekovski, On list edge-colorings of subcubic graphs, Manuscript, 1995. Zbl0957.05044
  119. [119] M. Juvan, B. Mohar, R. Skrekovski, List-total colorings of graphs, Manuscript, 1996. Zbl0911.05033
  120. [120] M. Juvan, B. Mohar, R. Skrekovski, Graphs of degree 4 are 5-edge-choosable, Manuscript, 1996. 
  121. [121] J. Kahn, Recent results on some not-so-recent hypergraph matching and covering problems, Extremal Problems for Finite Sets (P. Frankl et al., eds.), Bolyai Society Mathematical Studies 3, János Bolyai Math. Soc., Budapest, 1994, 305-353. Zbl0820.05050
  122. [122] J. Kahn, Asymptotically good list-colorings, Journal of Combinatorial Theory, Ser. A 73 (1996) 1-59. Zbl0851.05081
  123. [123] J. Kahn, Asymptotics of the list-chromatic index for multigraphs, Manuscript, 1996. Zbl0861.05026
  124. [124] J. Kahn, Private communication, June 1997. 
  125. [125] M. Katchalski, W. McCuaig, S. Seager, Ordered colourings, Discrete Mathematics 142 (1995) 141-154, doi: 10.1016/0012-365X(93)E0216-Q. 
  126. [126] H. Kierstead, W.T. Trotter, Planar graph coloring with an uncooperative partner, Journal of Graph Theory 18 (1994) 569-584. Zbl0809.05044
  127. [127] H. Kierstead, Zs. Tuza, Game chromatic number and tree width, Manuscript, 1995. 
  128. [128] J.H. Kim, On Brooks' theorem for sparse graphs, Combinatorics, Probability and Computing 4 (1995) 97-132, doi: 10.1017/S0963548300001528. Zbl0833.05030
  129. [129] A.V. Kostochka, Degree, girth and chromatic number, Combinatorics, Colloq. Math. Soc. János Bolyai 18, Keszthely, Hungary, 1976. North-Holland, 679-696. 
  130. [130] A.V. Kostochka, List edge chromatic number of graphs with large girth, Discrete Mathematics 101 (1992) 189-201, doi: 10.1016/0012-365X(92)90602-C. Zbl0766.05027
  131. [131] A.V. Kostochka, A.F. Sidorenko, Problem presented at the problem session, Fourth Czechoslovak Symposium on Combinatorics, Prachatice, 1990. Annals of Discrete Mathematics 51 (1992) 380. 
  132. [132] A.V. Kostochka, M. Stiebitz, B. Wirth, The colour theorems of Brooks and Gallai extended, Discrete Mathematics 162 (1996) 299-303, doi: 10.1016/0012-365X(95)00294-7. Zbl0871.05024
  133. [133] A.V. Kostochka, D.R. Woodall, Choosability and multicircuits, First draft, August 1997. Zbl0989.05041
  134. [134] J. Kratochvíl, Precoloring extension with fixed color bound, Acta Mathematica Universitatis Comenianae 62 (1993) 139-153. Zbl0821.05027
  135. [135] J. Kratochvíl, A. Seb o, Coloring precolored perfect graphs, Journal of Graph Theory, to appear. Zbl0876.05035
  136. [136] J. Kratochvíl, Zs. Tuza, Algorithmic complexity of list colorings, Discrete Applied Mathematics 50 (1994) 297-302, doi: 10.1016/0166-218X(94)90150-3. Zbl0807.68055
  137. [137] J. Kratochvíl, Zs. Tuza, M. Voigt, Choosing subsets from color sets, Discrete Mathematics, to appear. Zbl0956.05095
  138. [138] J. Kratochvíl, Zs. Tuza, M. Voigt, Brooks-type theorems for choosability with separation, Journal of Graph Theory, in print. Zbl0894.05016
  139. [139] M. Kubale, Some results concerning the complexity of restricted colorings of graphs, Discrete Applied Mathematics 36 (1992) 35-46, doi: 10.1016/0166-218X(92)90202-L. Zbl0755.05036
  140. [140] E.L. Lawler, A note on the complexity of the chromatic number problem, Information Processing Letters 5 (1976) 66-67, doi: 10.1016/0020-0190(76)90065-X. 
  141. [141] V.B. Le, A good characterization of cograph contractions, Manuscript, September 1996. 
  142. [142] L. Lovász, Combinatorial Problems and Exercises. Akadémiai Kiadó, Budapest, 1979. 
  143. [143] F. Maffray, Kernels in perfect line-graphs, Journal of Combinatorial Theory, Ser. B 55 (1992) 1-8. Zbl0694.05054
  144. [144] N.V.R. Mahadev, F.S. Roberts, P. Santhanakrishnan, 3-choosable complete bipartite graphs, Technical Report 49-91, Rutgers University, New Brunswick, NJ, 1991. 
  145. [145] O. Marcotte, P.D. Seymour, Extending an edge coloring, Journal of Graph Theory 14 (1990) 565-573, doi: 10.1002/jgt.3190140508. Zbl0705.05031
  146. [146] P. Mihók, An extension of Brooks' theorem, Fourth Czechoslovak Symposium on Combinatorics, Prachatice, 1990. Annals of Discrete Mathematics 51 (1992) 235-236. 
  147. [147] P. Mihók, Zs. Tuza, M. Voigt, Fractional P-colorings and the P-choice ratio, First draft, August 1997. 
  148. [148] M. Mirzakhani, A small non-4-choosable planar graph, Manuscript, 1996. Zbl0860.05029
  149. [149] J.W. Moon, L. Moser, On cliques in graphs, Israel Journal of Mathematics 3 (1965) 23-28, doi: 10.1007/BF02760024. Zbl0144.23205
  150. [150] C.St.J.A. Nash-Williams, An application of matroids to graph theory, Theory of Graphs (P. Rosenstiehl, ed.), Proc. Int. Symp., Roma, 1996, Gordon and Breach, New York, 1967, 263-265. 
  151. [151] P. O-Donnel, In preparation, 1995. (Communicated by N. Eaton, 1997.) 
  152. [152] J. Petersen, Die Theorie der regulären Graphs, Acta Math. 15 (1891) 193-220, doi: 10.1007/BF02392606. 
  153. [153] M. Richardson, Solutions of irreflexive relations, Annals of Mathematics 58 (1953) 573-580, doi: 10.2307/1969755. Zbl0053.02902
  154. [154] F.S. Roberts, T-colorings of graphs : recent results and open problems, Discrete Mathematics 93 (1991) 229-245, doi: 10.1016/0012-365X(91)90258-4. Zbl0751.05042
  155. [155] F.S. Roberts, New directions in graph theory (with an emphasis on the role of applications), Annals of Discrete Mathematics 55 (1993) 13-43, doi: 10.1016/S0167-5060(08)70373-X. Zbl0787.05089
  156. [156] N. Robertson, P. Seymour, Graph minors, II. Algorithmic aspects of tree-width, Journal of Algorithms 7 (1986) 309-322, doi: 10.1016/0196-6774(86)90023-4. Zbl0611.05017
  157. [157] H. Sachs, Elementary proof of the cycle-plus-triangles theorem, Combinatorics, Paul Erdős is Eighty (Volume 1) (D. Miklós et al., eds.), Bolyai Society Mathematical Studies 1, János Bolyai Math. Soc., Budapest, 1993, 347-359. Zbl0797.05047
  158. [158] T.J. Schaefer, On the complexity of some two-person perfect-information games, 16 (1978) 185-225. Zbl0383.90112
  159. [159] P. Scheffler, Die Baumweite von Graphen als ein Maß für die Komplizierheit algorithmischer Probleme, Report RMATH-04/89, K.-Weierstraß-Institut für Mathematik, Berlin, 1989. 
  160. [160] D.E. Scheim, The number of edge 3-colorings of a planar cubic graph as a permanent, Discrete Mathematics 8 (1974) 377-382, doi: 10.1016/0012-365X(74)90157-5. Zbl0281.05103
  161. [161] J.H. Schmerl, The list chromatic number of Euclidean space, Geombinatorics 5 (1995) 65-68. Zbl0847.05056
  162. [162] A. Schrijver, Theory of Linear and Integer Programming. Wiley, 1986. 
  163. [163] P.D. Seymour, Problem presented at the problem session, DIMACS Meeting on Polyhedral Combinatorics, Morristown, 1989. 
  164. [164] P.D. Seymour, A note on list arboricity, Manuscript, April 1996. 
  165. [165] C.E. Shannon, A theorem on coloring the lines of a network, Journal of Math. Phys. 28 (1948) 148-151. Zbl0032.43203
  166. [166] J. Shearer, A note on the independence number of triangle-free graphs, Discrete Mathematics 46 (1983) 83-87, doi: 10.1016/0012-365X(83)90273-X. Zbl0516.05053
  167. [167] J. Shearer, A note on the independence number of triangle-free graphs, II, Journal of Combinatorial Theory, Ser. B 53 (1991) 300-307. Zbl0753.05074
  168. [168] J. Shearer, On the independence number of sparse graphs, Random Structures and Algorithms 7 (1995) 269-271, doi: 10.1002/rsa.3240070305. Zbl0834.05030
  169. [169] A.M. Shende, B. Tesman, 3-choosability of K 5 , q , Congressus Numerantium 111 (1995) 193-221. Zbl0896.05027
  170. [170] R. Skrekovski, List improper colorings of planar graphs, To appear. Zbl0940.05027
  171. [171] T. Slivnik, Short proof of Galvin's theorem on the list-chromatic index of a bipartite multigraph, Combinatorics, Probability and Computing 5 (1996) 91-94, doi: 10.1017/S0963548300001851. Zbl0857.05034
  172. [172] L. Sun, A note on colouring of complete graphs, Quarterly Journal of Mathematics, Oxford (2) 46 (1995) 235-237, doi: 10.1093/qmath/46.2.235. Zbl0826.05029
  173. [173] J.J. Sylvester, On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, with three appendices, American Journal of Mathematics 1 (1878) 64-125, doi: 10.2307/2369436. Zbl10.0090.03
  174. [174] B.A. Tesman, T-Colorings, T-List Colorings, and Set T-Colorings of Graphs. Ph.D. Thesis, Department of Mathematics, Rutgers University, New Brunswick, NJ, October 1989. 
  175. [175] B.A. Tesman, List T-colorings of graphs, Discrete Applied Mathematics 45 (1993) 277-289, doi: 10.1016/0166-218X(93)90015-G. Zbl0788.05047
  176. [176] C. Thomassen, Every planar graph is 5-choosable, Journal of Combinatorial Theory, Ser. B 62 (1994) 180-181. Zbl0805.05023
  177. [177] C. Thomassen, 3-list-coloring planar graphs of girth 5, Journal of Combinatorial Theory, Ser. B 64 (1995) 101-107. Zbl0822.05029
  178. [178] C. Thomassen, Color-critical graphs on a fixed surface, Journal of Combinatorial Theory, Ser. B 70 (1997) 67-100. Zbl0883.05051
  179. [179] B. Toft, Color-critical graphs and hypergraphs, Journal of Combinatorial Theory, Ser. B 16 (1974) 145-161. Zbl0269.05117
  180. [180] S. Tsukiyama, M. Ide, H. Ariyshi, I. Shirakawa, A new algorithm for generating all the maximal independent sets, SIAM Journal on Computing 6 (1977) 505-517, doi: 10.1137/0206036. Zbl0364.05027
  181. [181] Zs. Tuza, Choice-perfect graphs and Hall numbers, In preparation. 
  182. [182] Zs. Tuza, M. Voigt, Lecture at the German Combinatorics Conference, Hamburg, 1994. 
  183. [183] Zs. Tuza, M. Voigt, On (a,b)-Choosability, Preprints of Twente Workshop, Enschede, The Netherlands, June 1995. 
  184. [184] Zs. Tuza, M. Voigt, Ranking problems on graphs, Manuscript, 1995. 
  185. [185] Zs. Tuza, M. Voigt, On a conjecture of Erdős, Rubin and Taylor, Tatra Mountains Mathematical Publications 9 (1996) 69-82. 
  186. [186] Zs. Tuza, M. Voigt, Every 2-choosable graph is (2m,m)-choosable, Journal of Graph Theory 22 (1996) 245-252, doi: 10.1002/(SICI)1097-0118(199607)22:3<245::AID-JGT5>3.0.CO;2-M Zbl0853.05034
  187. [187] Zs. Tuza, M. Voigt, List colorings and reducibility, Discrete Mathematics (1997) in print. Zbl0882.05055
  188. [188] L. Vigneron, Remarques sur les réseaux arbiques de classe 3 associés au probleme des quatre couleurs, C. R. Acad. Sci. Paris 223 (1946) 770-772. Zbl0060.41605
  189. [189] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Metody Diskret. Analiz. 3 (1964) 25-30. (in Russian) 
  190. [190] V.G. Vizing, Coloring the vertices of a graph in prescribed colors, Metody Diskret. Anal. v Teorii Kodov i Schem 29 (1976) 3-10. (In Russian) 
  191. [191] M. Voigt, List colourings of planar graphs, Discrete Mathematics 120 (1993) 215-219, doi: 10.1016/0012-365X(93)90579-I. Zbl0790.05030
  192. [192] M. Voigt, Unpublished conjecture, 1993. 
  193. [193] M. Voigt, A not 3-choosable planar graph without 3-cycles, Discrete Mathematics 146 (1995) 325-328, doi: 10.1016/0012-365X(94)00180-9. Zbl0843.05034
  194. [194] M. Voigt, On List Colourings and Choosability of Graphs. Habilitationsschrift, Technische Universität Ilmenau, Germany, March 1997. 
  195. [195] M. Voigt, B. Wirth, On 3-colorable non-4-choosable planar graphs, Journal of Graph Theory 24 (1997) 233-235, doi: 10.1002/(SICI)1097-0118(199703)24:3<233::AID-JGT4>3.0.CO;2-Q Zbl0868.05025
  196. [196] A. Waller, An upper bound for list T-colourings, Bulletin of the London Mathematical Society 28 (1996) 337-342, doi: 10.1112/blms/28.4.337. Zbl0854.05047
  197. [197] G.J. Woeginger, Unpublished conjecture, 1992. 
  198. [198] K. Xu, A special case of the edge-chromatic scheduling problem, Report ORWP 96/03, École Polytechnique Fédérale de Lausanne, 1996. 

Citations in EuDML Documents

top
  1. Tomáš Vetrík, List coloring of complete multipartite graphs
  2. Guo-Ping Zheng, Yu-Fa Shen, Zuo-Li Chen, Jin-Feng Lv, On choosability of complete multipartite graphs K 4 , 3 * t , 2 * ( k - 2 t - 2 ) , 1 * ( t + 1 )
  3. Wayne Goddard, Kirsti Wash, Honghai Xu, Worm Colorings
  4. Dominique de Werra, Daniel Kobler, Coloration de graphes : fondements et applications
  5. Dominique de Werra, Daniel Kobler, Coloration de graphes : fondements et applications
  6. Zsolt Tuza, Choice-Perfect Graphs
  7. Mieczysław Borowiecki, Izak Broere, Marietjie Frick, Peter Mihók, Gabriel Semanišin, A survey of hereditary properties of graphs

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.