Graph colorings with local constraints - a survey

Zsolt Tuza

Discussiones Mathematicae Graph Theory, Tome 17 (1997), p. 161-228 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 1997-01-01

Zbl 0923.05027

EUDML-ID : urn:eudml:doc:270527

Bibliographie

[000] [1] M. Ajtai, J. Komlós, E. Szemerédi, A note on Ramsey numbers, Journal of Combinatorial Theory, Ser. A 29 (1980) 354-360. | Zbl 0455.05045

[001] [2] M.O. Albertson, You can't paint yourself into a corner, Manuscript, 1997.

[002] [3] N. Alon, Choice numbers of graphs : A probabilistic approach, Combinatorics, Probability and Computing 1 (1992) 107-114, doi:10.1017/S0963548300000122.

[003] [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. | Zbl 0791.05034

[004] [5] N. Alon, Private communication, October 1995.

[005] [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. | Zbl 0611.05044

[006] [7] N. Alon, M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992) 125-134, doi: 10.1007/BF01204715. | Zbl 0756.05049

[007] [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. | Zbl 0877.05020

[008] [9] N. Alon, A. Zaks, T-choosability in graphs, Manuscript, 1996.

[009] [10] L.D. Andersen, Completing partial latin squares, Mat. Fys. Medd. Danske Vid. Selsk. 41 (1985) 23-69.

[010] [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. | Zbl 0821.05005

[011] [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. | Zbl 0666.68067

[012] [13] E. Arroyo, Thesis, Kennesaw State University, GA, in preparation.

[013] [14] J. Beck, On 3-chromatic hypergraphs, Discrete Mathematics 24 (1978) 127-137, doi: 10.1016/0012-365X(78)90191-7. | Zbl 0429.05055

[014] [15] C. Berge, Graphs. North-Holland, 1985.

[015] [16] E.R. Berlekamp, J.H. Conway, R.K. Guy, Winning Ways for your Mathematical Plays. Academic Press, 1982. | Zbl 0485.00025

[016] [17] M. Biró, M. Hujter, Zs. Tuza, Precoloring extension, Technical Report, Computer and Automation Institute, Budapest, 1990.

[017] [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.

[018] [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.

[019] [20] H.L. Bodlaender, On the complexity of some coloring games, 2 : 2 (1991) 133-147. | Zbl 0753.05061

[020] [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.

[021] [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. | Zbl 0822.68011

[022] [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. | Zbl 0785.90119

[023] [24] B. Bollobás, Chromatic number, girth and maximal degree, Discrete Mathematics 24 (1978) 311-314, doi: 10.1016/0012-365X(78)90102-4. | Zbl 0395.05034

[024] [25] B. Bollobás, The chromatic number of random graphs, Combinatorica 8 (1988) 49-55, doi: 10.1007/BF02122551. | Zbl 0666.05033

[025] [26] B. Bollobás, A.J. Harris, List-colourings of graphs, Graphs and Combinatorics 1 (1985) 115-127, doi: 10.1007/BF02582936. | Zbl 0606.05027

[026] [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. | Zbl 0674.05027

[027] [28 ] J.A. Bondy, R. Boppana, A. Siegel, Unpublished, 1989.

[028] [29] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications. Elsevier, New York, 1976. | Zbl 1226.05083

[029] [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.

[030] [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. | Zbl 0653.05029

[031] [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. | Zbl 0876.05032

[032] [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. | Zbl 0902.05026

[033] [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. | Zbl 0903.05022

[034] [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. | Zbl 0845.05046

[035] [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.

[036] [37] D.P. Bovet, P. Crescenzi, Introduction to the Theory of Complexity. Prentice Hall International Series in Computer Science, 1994. | Zbl 0809.68067

[037] [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. | Zbl 0027.26403

[038] [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. | Zbl 0696.05024

[039] [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. | Zbl 0553.05053

[040] [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. | Zbl 0674.05026

[041] [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. | Zbl 0538.05013

[042] [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. | Zbl 0575.68065

[043] [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. | Zbl 0722.03008

[044] [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. | Zbl 0596.05024

[045] [46] D. de Werra, Restricted models for timetabling, Discrete Mathematics 165/166 (1997) 161-170, doi: 10.1016/S0012-365X(96)00208-7. | Zbl 0876.90060

[046] [47] D. de Werra, The combinatorics of timetabling, 96 (1997) 504-513. | Zbl 0917.90190

[047] [48] D. de Werra, Mathematical programming models in chromatic scheduling, Manuscript, 1997.

[048] [49] J.H. Dinitz, W.J. Martin, The stipulation polynomial of a uniquely list-colorable graph, Australasian Journal of Combinatorics 11 (1995) 105-115. | Zbl 0826.05025

[049] [50] Q. Donner, On the number of list-colorings, Journal of Graph Theory 16 (1992) 239-245, doi: 10.1002/jgt.3190160307. | Zbl 0754.05038

[050] [51] M. Dror, G. Finke, S. Gravier, W. Kubiak, On the complexity of a restricted list-coloring problem, Manuscript, 1997. | Zbl 0928.05057

[051] [52] D.Z. Du, D.F. Hsu, F.K. Hwang, The Hamiltonian property of consecutive-d digraphs, 17 : 11 (1993) 61-63. | Zbl 0789.05040

[052] [53] P. Dukes, H. Emerson, G. MacGillivray, Undecidable generalized colouring problems, Journal of Combinatorial Mathematics and Combinatorial Computing, to appear. | Zbl 0897.05039

[053] [54] N. Eaton, Unpublished, 1996.

[054] [55] N. Eaton, T. Hull, Private communication, June 1997.

[055] [56] J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices, 69 (1965) 125-130.

[056] [57] J. Edmonds, D.R. Fulkerson, Transversals and matroid partition, 69 (1965) 147-153. | Zbl 0141.21801

[057] [58] M.N. Ellingham, L. Goddyn, List edge colourings of some 1-factorizable multigraphs, Combinatorica 16 (1996) 343-352, doi: 10.1007/BF01261320. | Zbl 0860.05035

[058] [59] P. Erdős, On a combinatorial problem, II, Acta Math. Acad. Sci. Hungar. 15 (1964) 445-447, doi: 10.1007/BF01897152.

[059] [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. | Zbl 0486.05001

[060] [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.

[061] [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.

[062] [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. | Zbl 0358.90021

[063] [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. | Zbl 0796.90082

[064] [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.

[065] [66] A.S. Finbow, B.L. Hartnell, A game related to covering by stars, Ars Combinatoria 16-A (1983) 189-198. | Zbl 0559.90095

[066] [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.

[067] [68] D. Gale, S. Shapley, College admissions and the stability of marriage, American Mathematical Monthly 69 (1962) 9-15, doi: 10.2307/2312726. | Zbl 0109.24403

[068] [69] T. Gallai, Kritische Graphen I, II, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963) 165-192 ; 373-395.

[069] [70] F. Galvin, The list chromatic index of a bipartite multigraph, Journal of Combinatorial Theory, Ser. B 63 (1995) 153-158. | Zbl 0826.05026

[070] [71] M.R. Garey, D.S. Johnson, Computers and Intractability - A Guide to the Theory of NP-Completeness. Freeman, New York, 1979. | Zbl 0411.68039

[071] [72] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.

[072] [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.

[073] [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. | Zbl 0853.05037

[074] [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. | Zbl 0888.05027

[075] [76] S. Gravier, F. Maffray, Graphs whose choice number is equal to their chromatic number, Manuscript, LSD2-IMAG, Grenoble, France, January 1995. | Zbl 0891.05031

[076] [77] H. Gröflin, Feasible graph coloring and a generalization of perfect graphs, Manuscript, University of Fribourg, 1992.

[077] [78] M. Grötschel, L. Lovász, A. Schrijver, Polynomial algorithms for perfect graphs, Annals of Discrete Mathematics 21 (1984) 325-356. | Zbl 0554.05041

[078] [79] M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin, Heidelberg, 1988. | Zbl 0634.05001

[079] [80] R.P. Gupta, The chromatic index and the degree of a graph, Notices of the American Mathematical Society 13 (1966) Abstract 66T-429.

[080] [81] S. Gutner, Choice Numbers of Graphs. M.Sc. Thesis, Tel Aviv University, 1992.

[081] [82] S. Gutner, The complexity of planar graph choosability, Manuscript, 1994, to appear in Discrete Mathematics. | Zbl 0865.05066

[082] [83] S. Gutner, M. Tarsi, Some results on (a:b)-choosability, To appear. | Zbl 1198.05049

[083] [94] R. Häggkvist, Towards a solution of the Dinitz problem ? Discrete Mathematics 75 (1989) 247-251. | Zbl 0669.05014

[084] [85] R. Häggkvist, Restricted edge-colourings of bipartite graphs, Combinatorics, Probability and Computing 5 (1996) 385-392, doi: 10.1017/S0963548300002133. | Zbl 0863.05039

[085] [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. | Zbl 0814.05038

[086] [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. | Zbl 0880.05035

[087] [88] Gy. Hajós, Über eine Konstruktion nicht n-färbbarer Graphen, Wiss. Z. Martin Luther Univ. Math.-Natur. Reihe 10 (1961) 116-117.

[088] [89] W.K. Hale, Frequency assignment : theory and applications, Proceedings of IEEE 68 (1980) 1497-1514, doi: 10.1109/PROC.1980.11899.

[089] [90] D. Hanson, G. MacGillivray, B. Toft, Choosability of bipartite graphs, Ars Combinatoria 44 (1996) 183-192. | Zbl 0889.05048

[090] [91] F. Harary, Graph Theory. Addison-Wesley, 1969.

[091] [92] F. Harary, Zs. Tuza, Two graph-colouring games, Bulletin of the Australian Mathematical Society 48 (1993) 141-149, doi: 10.1017/S0004972700015549.

[092] [93] A. Hertz, Slim graphs, Graphs and Combinatorics 5 (1989) 149-157, doi: 10.1007/BF01788666. | Zbl 0677.05065

[093] [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.

[094] [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. | Zbl 0934.05001

[095] [96] A.J.W. Hilton, P.D. Johnson, Jr., E.B. Wantland, The Hall number of a simple graph, Congressus Numerantium, to appear.

[096] [97] H.R. Hind, Restricted Edge-Colourings. Ph.D. Thesis, Peterhouse College, Cambridge, 1988.

[097] [98] D.G. Hoffman, P.D. Johnson, Jr., On the choice number of $K_{m,n}$, Congressus Numerantium 98 (1993) 105-111. | Zbl 0801.05027

[098] [99] D.G. Hoffman, P.D. Johnson, Jr., E.B. Wantland, Restricted choice numbers, Congressus Numerantium 105 (1994) 65-79.

[099] [100] I. Holyer, The NP-completeness of edge-coloring, SIAM Journal on Computing 10 (1981) 718-720, doi: 10.1137/0210055. | Zbl 0473.68034

[100] [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. | Zbl 0266.05114

[101] [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. | Zbl 0797.05019

[102] [103] M. Hujter, Zs. Tuza, Precoloring extension, II. Graph classes related to bipartite graphs, Acta Mathematica Universitatis Comenianae 62 (1993) 1-11.

[103] [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. | Zbl 0779.05025

[104] [105] M. Hujter, Zs. Tuza, Precoloring extension, III. Classes of perfect graphs, Combinatorics, Probability and Computing 5 (1996) 35-56, doi: 10.1017/S0963548300001826. | Zbl 0846.05034

[105] [106] M. Hujter, Zs. Tuza, Precoloring extension, IV. General bounds and list colorings, In preparation.

[106] [107] F. Jaeger, On the Penrose number of cubic diagrams, Discrete Mathematics 74 (1989) 85-97, doi: 10.1016/0012-365X(89)90201-X. | Zbl 0679.05029

[107] [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.

[108] [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.

[109] [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. | Zbl 0792.05053

[110] [111] T.R. Jensen, B. Toft, Graph Coloring Problems. Wiley Interscience, 1995.

[111] [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. | Zbl 0855.05055

[112] [113] A. Johansson, An improved upper bound on the choice number for triangle free graphs, Manuscript, January 1996.

[113] [114] A. Johansson, The choice number of sparse graphs, Preliminary version, April 1996.

[114] [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. | Zbl 0654.68086

[115] [116] P.D. Johnson, Jr., The choice number of the plane, Geombinatorics 3 (1994) 122-128. | Zbl 0848.05031

[116] [117] M. Juvan, B. Mohar, List colorings of outerplanar graphs, Manuscript, 1996.

[117] [118] M. Juvan, B. Mohar, R. Skrekovski, On list edge-colorings of subcubic graphs, Manuscript, 1995. | Zbl 0957.05044

[118] [119] M. Juvan, B. Mohar, R. Skrekovski, List-total colorings of graphs, Manuscript, 1996. | Zbl 0911.05033

[119] [120] M. Juvan, B. Mohar, R. Skrekovski, Graphs of degree 4 are 5-edge-choosable, Manuscript, 1996.

[120] [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. | Zbl 0820.05050

[121] [122] J. Kahn, Asymptotically good list-colorings, Journal of Combinatorial Theory, Ser. A 73 (1996) 1-59. | Zbl 0851.05081

[122] [123] J. Kahn, Asymptotics of the list-chromatic index for multigraphs, Manuscript, 1996. | Zbl 0861.05026

[123] [124] J. Kahn, Private communication, June 1997.

[124] [125] M. Katchalski, W. McCuaig, S. Seager, Ordered colourings, Discrete Mathematics 142 (1995) 141-154, doi: 10.1016/0012-365X(93)E0216-Q.

[125] [126] H. Kierstead, W.T. Trotter, Planar graph coloring with an uncooperative partner, Journal of Graph Theory 18 (1994) 569-584. | Zbl 0809.05044

[126] [127] H. Kierstead, Zs. Tuza, Game chromatic number and tree width, Manuscript, 1995.

[127] [128] J.H. Kim, On Brooks' theorem for sparse graphs, Combinatorics, Probability and Computing 4 (1995) 97-132, doi: 10.1017/S0963548300001528. | Zbl 0833.05030

[128] [129] A.V. Kostochka, Degree, girth and chromatic number, Combinatorics, Colloq. Math. Soc. János Bolyai 18, Keszthely, Hungary, 1976. North-Holland, 679-696.

[129] [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. | Zbl 0766.05027

[130] [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.

[131] [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. | Zbl 0871.05024

[132] [133] A.V. Kostochka, D.R. Woodall, Choosability and multicircuits, First draft, August 1997. | Zbl 0989.05041

[133] [134] J. Kratochvíl, Precoloring extension with fixed color bound, Acta Mathematica Universitatis Comenianae 62 (1993) 139-153. | Zbl 0821.05027

[134] [135] J. Kratochvíl, A. Seb o, Coloring precolored perfect graphs, Journal of Graph Theory, to appear. | Zbl 0876.05035

[135] [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. | Zbl 0807.68055

[136] [137] J. Kratochvíl, Zs. Tuza, M. Voigt, Choosing subsets from color sets, Discrete Mathematics, to appear. | Zbl 0956.05095

[137] [138] J. Kratochvíl, Zs. Tuza, M. Voigt, Brooks-type theorems for choosability with separation, Journal of Graph Theory, in print. | Zbl 0894.05016

[138] [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. | Zbl 0755.05036

[139] [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.

[140] [141] V.B. Le, A good characterization of cograph contractions, Manuscript, September 1996.

[141] [142] L. Lovász, Combinatorial Problems and Exercises. Akadémiai Kiadó, Budapest, 1979.

[142] [143] F. Maffray, Kernels in perfect line-graphs, Journal of Combinatorial Theory, Ser. B 55 (1992) 1-8. | Zbl 0694.05054

[143] [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.

[144] [145] O. Marcotte, P.D. Seymour, Extending an edge coloring, Journal of Graph Theory 14 (1990) 565-573, doi: 10.1002/jgt.3190140508. | Zbl 0705.05031

[145] [146] P. Mihók, An extension of Brooks' theorem, Fourth Czechoslovak Symposium on Combinatorics, Prachatice, 1990. Annals of Discrete Mathematics 51 (1992) 235-236.

[146] [147] P. Mihók, Zs. Tuza, M. Voigt, Fractional P-colorings and the P-choice ratio, First draft, August 1997.

[147] [148] M. Mirzakhani, A small non-4-choosable planar graph, Manuscript, 1996. | Zbl 0860.05029

[148] [149] J.W. Moon, L. Moser, On cliques in graphs, Israel Journal of Mathematics 3 (1965) 23-28, doi: 10.1007/BF02760024. | Zbl 0144.23205

[149] [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.

[150] [151] P. O-Donnel, In preparation, 1995. (Communicated by N. Eaton, 1997.)

[151] [152] J. Petersen, Die Theorie der regulären Graphs, Acta Math. 15 (1891) 193-220, doi: 10.1007/BF02392606.

[152] [153] M. Richardson, Solutions of irreflexive relations, Annals of Mathematics 58 (1953) 573-580, doi: 10.2307/1969755. | Zbl 0053.02902

[153] [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. | Zbl 0751.05042

[154] [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. | Zbl 0787.05089

[155] [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. | Zbl 0611.05017

[156] [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. | Zbl 0797.05047

[157] [158] T.J. Schaefer, On the complexity of some two-person perfect-information games, 16 (1978) 185-225. | Zbl 0383.90112

[158] [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.

[159] [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. | Zbl 0281.05103

[160] [161] J.H. Schmerl, The list chromatic number of Euclidean space, Geombinatorics 5 (1995) 65-68. | Zbl 0847.05056

[161] [162] A. Schrijver, Theory of Linear and Integer Programming. Wiley, 1986.

[162] [163] P.D. Seymour, Problem presented at the problem session, DIMACS Meeting on Polyhedral Combinatorics, Morristown, 1989.

[163] [164] P.D. Seymour, A note on list arboricity, Manuscript, April 1996.

[164] [165] C.E. Shannon, A theorem on coloring the lines of a network, Journal of Math. Phys. 28 (1948) 148-151. | Zbl 0032.43203

[165] [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. | Zbl 0516.05053

[166] [167] J. Shearer, A note on the independence number of triangle-free graphs, II, Journal of Combinatorial Theory, Ser. B 53 (1991) 300-307. | Zbl 0753.05074

[167] [168] J. Shearer, On the independence number of sparse graphs, Random Structures and Algorithms 7 (1995) 269-271, doi: 10.1002/rsa.3240070305. | Zbl 0834.05030

[168] [169] A.M. Shende, B. Tesman, 3-choosability of $K_{5,q}$, Congressus Numerantium 111 (1995) 193-221. | Zbl 0896.05027

[169] [170] R. Skrekovski, List improper colorings of planar graphs, To appear. | Zbl 0940.05027

[170] [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. | Zbl 0857.05034

[171] [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. | Zbl 0826.05029

[172] [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. | Zbl 10.0090.03

[173] [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.

[174] [175] B.A. Tesman, List T-colorings of graphs, Discrete Applied Mathematics 45 (1993) 277-289, doi: 10.1016/0166-218X(93)90015-G. | Zbl 0788.05047

[175] [176] C. Thomassen, Every planar graph is 5-choosable, Journal of Combinatorial Theory, Ser. B 62 (1994) 180-181. | Zbl 0805.05023

[176] [177] C. Thomassen, 3-list-coloring planar graphs of girth 5, Journal of Combinatorial Theory, Ser. B 64 (1995) 101-107. | Zbl 0822.05029

[177] [178] C. Thomassen, Color-critical graphs on a fixed surface, Journal of Combinatorial Theory, Ser. B 70 (1997) 67-100. | Zbl 0883.05051

[178] [179] B. Toft, Color-critical graphs and hypergraphs, Journal of Combinatorial Theory, Ser. B 16 (1974) 145-161. | Zbl 0269.05117

[179] [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. | Zbl 0364.05027

[180] [181] Zs. Tuza, Choice-perfect graphs and Hall numbers, In preparation.

[181] [182] Zs. Tuza, M. Voigt, Lecture at the German Combinatorics Conference, Hamburg, 1994.

[182] [183] Zs. Tuza, M. Voigt, On (a,b)-Choosability, Preprints of Twente Workshop, Enschede, The Netherlands, June 1995.

[183] [184] Zs. Tuza, M. Voigt, Ranking problems on graphs, Manuscript, 1995.

[184] [185] Zs. Tuza, M. Voigt, On a conjecture of Erdős, Rubin and Taylor, Tatra Mountains Mathematical Publications 9 (1996) 69-82.

[185] [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 | Zbl 0853.05034

[186] [187] Zs. Tuza, M. Voigt, List colorings and reducibility, Discrete Mathematics (1997) in print. | Zbl 0882.05055

[187] [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. | Zbl 0060.41605

[188] [189] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Metody Diskret. Analiz. 3 (1964) 25-30. (in Russian)

[189] [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)

[190] [191] M. Voigt, List colourings of planar graphs, Discrete Mathematics 120 (1993) 215-219, doi: 10.1016/0012-365X(93)90579-I. | Zbl 0790.05030

[191] [192] M. Voigt, Unpublished conjecture, 1993.

[192] [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. | Zbl 0843.05034

[193] [194] M. Voigt, On List Colourings and Choosability of Graphs. Habilitationsschrift, Technische Universität Ilmenau, Germany, March 1997.

[194] [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 | Zbl 0868.05025

[195] [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. | Zbl 0854.05047

[196] [197] G.J. Woeginger, Unpublished conjecture, 1992.

[197] [198] K. Xu, A special case of the edge-chromatic scheduling problem, Report ORWP 96/03, École Polytechnique Fédérale de Lausanne, 1996.