摘要: The problem of properly coloring the vertices (or edges) a graph using for each vertex edge) color from prescribed list permissible colors, received considerable amount attention. Here we describe techniques applied in study this subject, which combine combinatorial, algebraic and probabilistic methods, discuss several intriguing conjectures open problems. This is mainly survey recent less results area, but it contains new as well. ∗Research supported part by United States Israel BSF Grant. Appeared ”Surveys Combinatorics”, Proc. 14 British Combinatorial Conference, London Mathematical Society Lecture Notes Series 187, edited K. Walker, Cambridge University Press, 1993, 1-33.
sci-hub.st 参考文章(32)
L. Lovász, Bounding the Independence Number of a Graph North-holland Mathematics Studies. ,vol. 66, pp. 213- 223 ,(1982) , 10.1016/S0304-0208(08)72453-8
C. Berge, Graphs and hypergraphs ,(1973)
László Lovász, Combinatorial problems and exercises ,(1979)
Roland Häggkvist, Towards a solution of the dinitz problem? Discrete Mathematics. ,vol. 75, pp. 247- 251 ,(1989) , 10.1016/0012-365X(89)90091-5
David E. Scheim, The number of edge 3-colorings of a planar cubic graph as a permanent Discrete Mathematics. ,vol. 8, pp. 377- 382 ,(1974) , 10.1016/0012-365X(74)90157-5
Shuo-Yen Robert Li, Wen-Ch’ing Winnie Li, Independence numbers of graphs and generators of ideals Combinatorica. ,vol. 1, pp. 55- 61 ,(1981) , 10.1007/BF02579177
J. Beck, On 3-chromatic hypergraphs Discrete Mathematics. ,vol. 24, pp. 127- 137 ,(1978) , 10.1016/0012-365X(78)90191-7
Roland Häggkvist, Amanda Chetwynd, Some upper bounds on the total and list chromatic numbers of multigraphs Journal of Graph Theory. ,vol. 16, pp. 503- 516 ,(1992) , 10.1002/JGT.3190160510
B. Bollobás, H.R. Hind, A new upper bound for the list chromatic number Discrete Mathematics. ,vol. 74, pp. 65- 75 ,(1989) , 10.1016/0012-365X(89)90199-4
H. R. Hind, An upper bound for the total chromatic number Graphs and Combinatorics. ,vol. 6, pp. 153- 159 ,(1990) , 10.1007/BF01787726