# Graph colorings with local constraints - a survey

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

top

## 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.

top

## 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.