PDF

Discussiones Mathematicae Graph Theory  17(2) (1997) 161-228
DOI: https://doi.org/10.7151/dmgt.1049

GRAPH COLORINGS WITH LOCAL CONSTRAINTS      A SURVEY

Zsolt Tuza

Computer and Automation Institute
Hungarian Academy of Sciences
H-1111 Budapest, Kende u. 13-17, Hungary
e-mail: tuza@lutra.sztaki.hu

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.

Keywords: graph coloring, list coloring, choice number, precoloring extension, complexity of algorithms, chromatic number.

1991 Mathematics Subject Classification: Primary 05--02, 05C15, Secondary 68R10

Contents

0.  Introduction	163
0.1  Standard Definitions	165
0.2  Notation for Vertex Colorings	165
0.3  Some Variations	167
0.4  Small Uncolorable Graphs	167
1.  General Results	168
1.1  Equivalent Formulations	168
1.2  Complete Bipartite Graphs and the Construction of Hajós	170
1.3  Typical Behavior of the Choice Number	172
1.4  Unions of Graphs and the (am,bm)-Conjecture	173
1.5  Graphs and Their Complements	175
2.  Vertex Degrees	176
2.1  The Theorems of Brooks and Gallai	177
2.2  Lower Bounds on the Choice Number	180
2.3  Graph Polynomials	181
2.4  Orientations and Eulerian Subdigraphs	183
3.  Comparisons of Coloring Parameters	185
3.1  Planar Graphs	186
3.2  Graphs with Equal Chromatic and Choice Number	188
3.3  Edge and Total Colorings	191
3.4  Choice Ratio and Fractional Chromatic Number	197
3.5  The Chromatic Polynomial	198
4.  Algorithmic Complexity	200
4.1  Precoloring Extension	202
4.2  Good Characterizations	204
4.3  List Colorings	206
4.4  Choosability	211
4.5  Graph Coloring Games	213

Acknowledgements

I am indebted to N. Alon, J. A. Bondy, M. Hujter, T. R. Jensen, H. Kierstead, J. Kratochví l, P. Mihók, C. Thomassen, B. Toft, and M. Voigt for fruitful and inspirative discussions on the subject, to G. Bacsó, K. M. Hangos, and T. R. Jensen for their many valuable comments on the first version of the paper, and to N. Eaton, C. N. Jagger, and A.V. Kostochka for useful short remarks. I thank the authors of results cited here but not published so far, for kindly informing me about their most recent works. Also, support from the Konrad-Zuse-Zentrum für Informationstechnik Berlin is thankfully acknowledged, where part of this research was carried out.

References

[1]	M. Ajtai, J. Komlós, E. Szemerédi, A note on Ramsey numbers ,  Journal of Combinatorial Theory, Ser. A 29 (1980) 354-360.
[2]	M.O. Albertson, You can't paint yourself into a corner ,  Manuscript, 1997.
[3]	N. Alon, Choice numbers of graphs : A probabilistic approach ,  Combinatorics, Probability and Computing 1 (1992) 107-114, doi: 10.1017/S0963548300000122.
[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.
[5]	N. Alon, Private communication, October 1995.
[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.
[7]	N. Alon, M. Tarsi, Colorings and orientations of graphs ,  Combinatorica 12 (1992) 125-134, doi: 10.1007/BF01204715.
[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.
[9]	N. Alon, A. Zaks, T-choosability in graphs ,  Manuscript, 1996.
[10]	L.D. Andersen, Completing partial latin squares ,  Mat. Fys. Medd. Danske Vid. Selsk. 41 (1985) 23-69.
[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.
[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.
[13]	E. Arroyo, Thesis, Kennesaw State University, GA, in preparation.
[14]	J. Beck, On 3-chromatic hypergraphs ,  Discrete Mathematics 24 (1978) 127-137, doi: 10.1016/0012-365X(78)90191-7.
[15]	C. Berge, Graphs. North-Holland, 1985.
[16]	E.R. Berlekamp, J.H. Conway, R.K. Guy, Winning Ways for your Mathematical Plays. Academic Press, 1982.
[17]	M. Biró, M. Hujter, Zs. Tuza, Precoloring extension ,  Technical Report, Computer and Automation Institute, Budapest, 1990.
[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]	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]	H.L. Bodlaender, On the complexity of some coloring games ,  2 : 2 (1991) 133-147.
[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]	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.
[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.
[24]	B. Bollobás, Chromatic number, girth and maximal degree ,  Discrete Mathematics 24 (1978) 311-314, doi: 10.1016/0012-365X(78)90102-4.
[25]	B. Bollobás, The chromatic number of random graphs ,  Combinatorica 8 (1988) 49-55, doi: 10.1007/BF02122551.
[26]	B. Bollobás, A.J. Harris, List-colourings of graphs ,  Graphs and Combinatorics 1 (1985) 115-127, doi: 10.1007/BF02582936.
[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.
[28 ]	J.A. Bondy, R. Boppana, A. Siegel, Unpublished, 1989.
[29]	J.A. Bondy, U.S.R. Murty, Graph Theory with Applications. Elsevier, New York, 1976.
[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]	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.
[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.
[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.
[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.
[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.
[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]	D.P. Bovet, P. Crescenzi, Introduction to the Theory of Complexity. Prentice Hall International Series in Computer Science, 1994.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[46]	D. de Werra, Restricted models for timetabling ,  Discrete Mathematics 165/166 (1997) 161-170, doi: 10.1016/S0012-365X(96)00208-7.
[47]	D. de Werra, The combinatorics of timetabling ,  96 (1997) 504-513.
[48]	D. de Werra, Mathematical programming models in chromatic scheduling ,  Manuscript, 1997.
[49]	J.H. Dinitz, W.J. Martin, The stipulation polynomial of a uniquely list-colorable graph ,  Australasian Journal of Combinatorics 11 (1995) 105-115.
[50]	Q. Donner, On the number of list-colorings ,  Journal of Graph Theory 16 (1992) 239-245, doi: 10.1002/jgt.3190160307.
[51]	M. Dror, G. Finke, S. Gravier, W. Kubiak, On the complexity of a restricted list-coloring problem ,  Manuscript, 1997.
[52]	D.Z. Du, D.F. Hsu, F.K. Hwang, The Hamiltonian property of consecutive-d digraphs ,  17 : 11 (1993) 61-63.
[53]	P. Dukes, H. Emerson, G. MacGillivray, Undecidable generalized colouring problems ,  Journal of Combinatorial Mathematics and Combinatorial Computing , to appear.
[54]	N. Eaton, Unpublished, 1996.
[55]	N. Eaton, T. Hull, Private communication, June 1997.
[56]	J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices ,  69 (1965) 125-130.
[57]	J. Edmonds, D.R. Fulkerson, Transversals and matroid partition ,  69 (1965) 147-153.
[58]	M.N. Ellingham, L. Goddyn, List edge colourings of some 1-factorizable multigraphs ,  Combinatorica 16 (1996) 343-352, doi: 10.1007/BF01261320.
[59]	P. Erdős, On a combinatorial problem, II ,  Acta Math. Acad. Sci. Hungar. 15 (1964) 445-447, doi: 10.1007/BF01897152.
[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.
[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]	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]	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.
[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.
[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]	A.S. Finbow, B.L. Hartnell, A game related to covering by stars ,  Ars Combinatoria 16-A (1983) 189-198.
[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]	D. Gale, S. Shapley, College admissions and the stability of marriage ,  American Mathematical Monthly 69 (1962) 9-15, doi: 10.2307/2312726.
[69]	T. Gallai, Kritische Graphen I, II ,  Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963) 165-192 ;  373-395.
[70]	F. Galvin, The list chromatic index of a bipartite multigraph ,  Journal of Combinatorial Theory, Ser. B 63 (1995) 153-158.
[71]	M.R. Garey, D.S. Johnson, Computers and Intractability - A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.
[72]	M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.
[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]	S. Gravier, A Hajós-like theorem for list coloring ,  Discrete Mathematics 152 (1996) 299-302, doi: 10.1016/0012-365X(95)00350-6.
[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.
[76]	S. Gravier, F. Maffray, Graphs whose choice number is equal to their chromatic number ,  Manuscript, LSD2-IMAG, Grenoble, France, January 1995.
[77]	H. Gröflin, Feasible graph coloring and a generalization of perfect graphs ,  Manuscript, University of Fribourg, 1992.
[78]	M. Grötschel, L. Lovász, A. Schrijver, Polynomial algorithms for perfect graphs ,  Annals of Discrete Mathematics 21 (1984) 325-356.
[79]	M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin, Heidelberg, 1988.
[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]	S. Gutner, Choice Numbers of Graphs. M.Sc. Thesis, Tel Aviv University, 1992.
[82]	S. Gutner, The complexity of planar graph choosability ,  Manuscript, 1994, to appear in Discrete Mathematics .
[83]	S. Gutner, M. Tarsi, Some results on (a:b)-choosability ,  To appear.
[94]	R. Häggkvist, Towards a solution of the Dinitz problem ?   Discrete Mathematics 75 (1989) 247-251.
[85]	R. Häggkvist, Restricted edge-colourings of bipartite graphs ,  Combinatorics, Probability and Computing 5 (1996) 385-392, doi: 10.1017/S0963548300002133.
[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.
[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.
[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]	W.K. Hale, Frequency assignment : theory and applications ,  Proceedings of IEEE 68 (1980) 1497-1514, doi: 10.1109/PROC.1980.11899.
[90]	D. Hanson, G. MacGillivray, B. Toft, Choosability of bipartite graphs ,  Ars Combinatoria 44 (1996) 183-192.
[91]	F. Harary, Graph Theory. Addison-Wesley, 1969.
[92]	F. Harary, Zs. Tuza, Two graph-colouring games ,  Bulletin of the Australian Mathematical Society 48 (1993) 141-149, doi: 10.1017/S0004972700015549.
[93]	A. Hertz, Slim graphs ,  Graphs and Combinatorics 5 (1989) 149-157, doi: 10.1007/BF01788666.
[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]	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.
[96]	A.J.W. Hilton, P.D. Johnson, Jr., E.B. Wantland, The Hall number of a simple graph ,  Congressus Numerantium , to appear.
[97]	H.R. Hind, Restricted Edge-Colourings. Ph.D. Thesis, Peterhouse College, Cambridge, 1988.
[98]	D.G. Hoffman, P.D. Johnson, Jr., On the choice number of Km,n ,  Congressus Numerantium 98 (1993) 105-111.
[99]	D.G. Hoffman, P.D. Johnson, Jr., E.B. Wantland, Restricted choice numbers ,  Congressus Numerantium 105 (1994) 65-79.
[100]	I. Holyer, The NP-completeness of edge-coloring ,  SIAM Journal on Computing 10 (1981) 718-720, doi: 10.1137/0210055.
[101]	J. Hopcroft, R.M. Karp, An n5/2 algorithm for maximum matching in bipartite graphs ,  SIAM Journal on Computing 2 (1973) 225-231, doi: 10.1137/0202019.
[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.
[103]	M. Hujter, Zs. Tuza, Precoloring extension, II. Graph classes related to bipartite graphs ,  Acta Mathematica Universitatis Comenianae 62 (1993) 1-11.
[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.
[105]	M. Hujter, Zs. Tuza, Precoloring extension, III. Classes of perfect graphs ,  Combinatorics, Probability and Computing 5 (1996) 35-56, doi: 10.1017/S0963548300001826.
[106]	M. Hujter, Zs. Tuza, Precoloring extension, IV. General bounds and list colorings ,  In preparation.
[107]	F. Jaeger, On the Penrose number of cubic diagrams ,  Discrete Mathematics 74 (1989) 85-97, doi: 10.1016/0012-365X(89)90201-X.
[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]	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]	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.
[111]	T.R. Jensen, B. Toft, Graph Coloring Problems. Wiley Interscience, 1995.
[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.
[113]	A. Johansson, An improved upper bound on the choice number for triangle free graphs ,  Manuscript, January 1996.
[114]	A. Johansson, The choice number of sparse graphs ,  Preliminary version, April 1996.
[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.
[116]	P.D. Johnson, Jr., The choice number of the plane ,  Geombinatorics 3 (1994) 122-128.
[117]	M. Juvan, B. Mohar, List colorings of outerplanar graphs ,  Manuscript, 1996.
[118]	M. Juvan, B. Mohar, R. Skrekovski, On list edge-colorings of subcubic graphs ,  Manuscript, 1995.
[119]	M. Juvan, B. Mohar, R. Skrekovski, List-total colorings of graphs ,  Manuscript, 1996.
[120]	M. Juvan, B. Mohar, R. Skrekovski, Graphs of degree 4 are 5-edge-choosable ,  Manuscript, 1996.
[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.
[122]	J. Kahn, Asymptotically good list-colorings ,  Journal of Combinatorial Theory, Ser. A 73 (1996) 1-59.
[123]	J. Kahn, Asymptotics of the list-chromatic index for multigraphs ,  Manuscript, 1996.
[124]	J. Kahn, Private communication, June 1997.
[125]	M. Katchalski, W. McCuaig, S. Seager, Ordered colourings ,  Discrete Mathematics 142 (1995) 141-154, doi: 10.1016/0012-365X(93)E0216-Q.
[126]	H. Kierstead, W.T. Trotter, Planar graph coloring with an uncooperative partner ,  Journal of Graph Theory 18 (1994) 569-584.
[127]	H. Kierstead, Zs. Tuza, Game chromatic number and tree width ,  Manuscript, 1995.
[128]	J.H. Kim, On Brooks' theorem for sparse graphs ,  Combinatorics, Probability and Computing 4 (1995) 97-132, doi: 10.1017/S0963548300001528.
[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]	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.
[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]	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.
[133]	A.V. Kostochka, D.R. Woodall, Choosability and multicircuits, First draft, August 1997.
[134]	J. Kratochvíl, Precoloring extension with fixed color bound ,  Acta Mathematica Universitatis Comenianae 62 (1993) 139-153.
[135]	J. Kratochvíl, A. Seb o, Coloring precolored perfect graphs ,  Journal of Graph Theory , to appear.
[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.
[137]	J. Kratochvíl, Zs. Tuza, M. Voigt, Choosing subsets from color sets ,  Discrete Mathematics , to appear.
[138]	J. Kratochvíl, Zs. Tuza, M. Voigt, Brooks-type theorems for choosability with separation ,  Journal of Graph Theory, in print.
[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.
[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]	V.B. Le, A good characterization of cograph contractions ,  Manuscript, September 1996.
[142]	L. Lovász, Combinatorial Problems and Exercises. Akadémiai Kiadó, Budapest, 1979.
[143]	F. Maffray, Kernels in perfect line-graphs ,  Journal of Combinatorial Theory, Ser. B 55 (1992) 1-8.
[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]	O. Marcotte, P.D. Seymour, Extending an edge coloring ,  Journal of Graph Theory 14 (1990) 565-573, doi: 10.1002/jgt.3190140508.
[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]	P. Mihók, Zs. Tuza, M. Voigt, Fractional P-colorings and the P-choice ratio ,  First draft, August 1997.
[148]	M. Mirzakhani, A small non-4-choosable planar graph ,  Manuscript, 1996.
[149]	J.W. Moon, L. Moser, On cliques in graphs ,  Israel Journal of Mathematics 3 (1965) 23-28, doi: 10.1007/BF02760024.
[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]	P. O-Donnel, In preparation, 1995. (Communicated by N. Eaton, 1997.)
[152]	J. Petersen, Die Theorie der regulären Graphs ,  Acta Math. 15 (1891) 193-220, doi: 10.1007/BF02392606.
[153]	M. Richardson, Solutions of irreflexive relations ,  Annals of Mathematics 58 (1953) 573-580, doi: 10.2307/1969755.
[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.
[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.
[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.
[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.
[158]	T.J. Schaefer, On the complexity of some two-person perfect-information games ,  16 (1978) 185-225.
[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]	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.
[161]	J.H. Schmerl, The list chromatic number of Euclidean space ,  Geombinatorics 5 (1995) 65-68.
[162]	A. Schrijver, Theory of Linear and Integer Programming. Wiley, 1986.
[163]	P.D. Seymour, Problem presented at the problem session, DIMACS Meeting on Polyhedral Combinatorics, Morristown, 1989.
[164]	P.D. Seymour, A note on list arboricity ,  Manuscript, April 1996.
[165]	C.E. Shannon, A theorem on coloring the lines of a network ,  Journal of Math. Phys. 28 (1948) 148-151.
[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.
[167]	J. Shearer, A note on the independence number of triangle-free graphs, II ,  Journal of Combinatorial Theory, Ser. B 53 (1991) 300-307.
[168]	J. Shearer, On the independence number of sparse graphs ,  Random Structures and Algorithms 7 (1995) 269-271, doi: 10.1002/rsa.3240070305.
[169]	A.M. Shende, B. Tesman, 3-choosability of K5,q ,  Congressus Numerantium 111 (1995) 193-221.
[170]	R. Skrekovski, List improper colorings of planar graphs ,  To appear.
[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.
[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.
[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.
[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]	B.A. Tesman, List T-colorings of graphs ,  Discrete Applied Mathematics 45 (1993) 277-289, doi: 10.1016/0166-218X(93)90015-G.
[176]	C. Thomassen, Every planar graph is 5-choosable ,  Journal of Combinatorial Theory, Ser. B 62 (1994) 180-181.
[177]	C. Thomassen, 3-list-coloring planar graphs of girth 5 ,  Journal of Combinatorial Theory, Ser. B 64 (1995) 101-107.
[178]	C. Thomassen, Color-critical graphs on a fixed surface ,  Journal of Combinatorial Theory, Ser. B 70 (1997) 67-100.
[179]	B. Toft, Color-critical graphs and hypergraphs ,  Journal of Combinatorial Theory, Ser. B 16 (1974) 145-161.
[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.
[181]	Zs. Tuza, Choice-perfect graphs and Hall numbers ,  In preparation.
[181]	Zs. Tuza, M. Voigt, Lecture at the German Combinatorics Conference, Hamburg, 1994.
[182]	Zs. Tuza, M. Voigt, On (a,b)-Choosability ,  Preprints of Twente Workshop, Enschede, The Netherlands, June 1995.
[183]	Zs. Tuza, M. Voigt, Ranking problems on graphs ,  Manuscript, 1995.
[184]	Zs. Tuza, M. Voigt, On a conjecture of Erdős, Rubin and Taylor ,  Tatra Mountains Mathematical Publications 9 (1996) 69-82.
[185]	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.
[186]	Zs. Tuza, M. Voigt, List colorings and reducibility ,  Discrete Mathematics (1997) in print.
[187]	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.
[188]	V.G. Vizing, On an estimate of the chromatic class of a p-graph ,  Metody Diskret. Analiz. 3 (1964) 25-30. (in Russian)
[189]	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)
[190]	M. Voigt, List colourings of planar graphs ,  Discrete Mathematics 120 (1993) 215-219, doi: 10.1016/0012-365X(93)90579-I.
[191]	M. Voigt, Unpublished conjecture, 1993.
[192]	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.
[193]	M. Voigt, On List Colourings and Choosability of Graphs. Habilitationsschrift, Technische Universität Ilmenau, Germany, March 1997.
[194]	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.
[195]	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.
[196]	G.J. Woeginger, Unpublished conjecture, 1992.
[197]	K. Xu, A special case of the edge-chromatic scheduling problem ,  Report ORWP 96/03, École Polytechnique Fédérale de Lausanne, 1996.