×

zbMATH — the first resource for mathematics

Randomly colouring graphs (a combinatorial view). (English) Zbl 1302.05060
Summary: The application of the probabilistic method to graph colouring has been yielding interesting results for more than 40 years. Several probabilistic tools are presented in this survey, ranging from the basic to the more advanced. For each of them, an application to a graph colouring problem is presented in detail. In this way, not only is the general idea of the method exposed, but also are the concrete details arising with its application. Further, this allows us to introduce some important variants of the usual graph colouring notion (with some related open questions), and at the same time to illustrate the variety of the probabilistic technics. The survey tries to be self-contained.

MSC:
05C15 Coloring of graphs and hypergraphs
05C80 Random graphs (graph-theoretic aspects)
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N., A parallel algorithmic version of the local lemma, (), 586-593
[2] Alon, N., Degrees and choice numbers, Random structures algorithms, 16, 4, 364-368, (2000) · Zbl 0958.05049
[3] Alon, N.; Dinur, I.; Friedgut, E.; Sudakov, B., Graph products, Fourier analysis and spectral techniques, Geom. funct. anal., 14, 5, 913-940, (2004) · Zbl 1056.05104
[4] Alon, N.; Grytczuk, J.; Hałuszczak, M.; Riordan, O., Nonrepetitive colorings of graphs, Random structures algorithms, 21, 3-4, 336-346, (2002), Random structures and algorithms (Poznan, 2001) · Zbl 1018.05032
[5] Alon, N.; Kalai, G.; Ricklin, M.; Stockmeyer, L., Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling, Theoret. comput. sci., 130, 1, 175-201, (1994) · Zbl 0834.68042
[6] Alon, N.; Krivelevich, M.; Sudakov, B., Subgraphs with a large cochromatic number, J. graph theory, 25, 4, 295-297, (1997) · Zbl 0882.05061
[7] Alon, N.; Krivelevich, M.; Sudakov, B., Coloring graphs with sparse neighborhoods, J. combin. theory ser. B, 77, 1, 73-82, (1999) · Zbl 1026.05043
[8] Alon, N.; McDiarmid, C.; Reed, B., Acyclic coloring of graphs, Random structures algorithms, 2, 3, 277-288, (1991) · Zbl 0735.05036
[9] Alon, N.; Mohar, B., The chromatic number of graph powers, Combin. probab. comput., 11, 1, 1-10, (2002) · Zbl 0991.05042
[10] Alon, N.; Orlitsky, A., Source coding and graph entropies, IEEE trans. inform. theory, 42, 5, 1329-1339, (1996) · Zbl 0868.94017
[11] Alon, N.; Spencer, J., (), With an appendix on the life and work of Paul Erdős · Zbl 1148.05001
[12] Alon, N.; Sudakov, B.; Zaks, A., Acyclic edge colorings of graphs, J. graph theory, 37, 3, 157-167, (2001) · Zbl 0996.05050
[13] Appel, K.; Haken, W., Every planar map is four colorable. I. discharging, Illinois J. math., 21, 3, 429-490, (1977) · Zbl 0387.05009
[14] Appel, K.; Haken, W.; Koch, J., Every planar map is four colorable. II. reducibility, Illinois J. math., 21, 3, 491-567, (1977) · Zbl 0387.05010
[15] Babilon, R.; Jelínek, V.; Král’, D.; Valtr, P., Labelings of graphs with fixed and variable edge-weights, SIAM J. discrete math., 21, 3, 688-706, (2007), (electronic) · Zbl 1141.05036
[16] Beck, J., An algorithmic approach to the lovász local lemma. I, Random structures algorithms, 2, 4, 343-365, (1991) · Zbl 0756.05080
[17] Beckner, W., Inequalities in Fourier analysis, Ann. of math. (2), 102, 1, 159-182, (1975) · Zbl 0338.42017
[18] M. Behzad, Graphs and their chromatic numbers, Doctoral thesis, Michigan State University, 1965
[19] Bella, P.; Král’, D.; Mohar, B; Quittnerová, K., Labeling planar graphs with a condition at distance two, European J. combin., 28, 8, 2201-2239, (2007) · Zbl 1127.05089
[20] Bellare, M.; Goldreich, O.; Sudan, M., Free bits, PCPs, and nonapproximability—towards tight results, SIAM J. comput., 27, 3, 804-915, (1998), (electronic) · Zbl 0912.68041
[21] Bollobás, B., Chromatic number, girth and maximal degree, Discrete math., 24, 3, 311-314, (1978) · Zbl 0395.05034
[22] Bollobás, B., ()
[23] Bonami, A., Étude des coefficients de Fourier des fonctions de \(l^p(g)\), Ann. inst. Fourier (Grenoble), 20, fasc. 2, 335-402, (1970) · Zbl 0195.42501
[24] O.V. Borodin, A criterion of chromaticity of a degree prescription, in: Abstracts of IV All-Union Conf. on Theoretical Cybernetics, Novosibirsk, 1977, pp. 127-128 (in Russian)
[25] Borodin, O.V., On the total coloring of planar graphs, J. reine angew. math., 394, 180-185, (1989) · Zbl 0653.05029
[26] Borodin, O.V.; Kostochka, A.V., On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density, J. combin. theory ser. B, 23, 2-3, 247-250, (1977) · Zbl 0336.05104
[27] Borodin, O.V.; Kostochka, A.V.; Woodall, D.R., List edge and List total colourings of multigraphs, J. combin. theory ser. B, 71, 2, 184-204, (1997) · Zbl 0876.05032
[28] Borodin, O.V.; Kostochka, A.V.; Woodall, D.R., Total colorings of planar graphs with large maximum degree, J. graph theory, 26, 1, 53-59, (1997) · Zbl 0883.05053
[29] Brègman, L.M., Certain properties of nonnegative matrices and their permanents, Dokl. akad. nauk SSSR, 211, 27-30, (1973) · Zbl 0293.15010
[30] Brooks, R.L., On colouring the nodes of a network, Proc. Cambridge philos. soc., 37, 194-197, (1941) · Zbl 0027.26403
[31] Calamoneri, T., The \(L(h, k)\)-labelling problem: A survey and annotated bibliography, The computer J., 49, 5, 585-608, (2006), URL: http://www.dsi.uniromal.it/ calamo/survey.html
[32] Gonçalves, D., On the \(L(p, 1)\)-labelling of graphs, Discrete math., 308, 8, 1405-1414, (2008) · Zbl 1135.05065
[33] J. Campbell, Fourier analysis—theory and applications. URL: http://ocw.mit.edu/OcwWeb/Mathematics/18-103Spring2004/LectureNotes/index.htm, 2004
[34] Catlin, P.A., A bound on the chromatic number of a graph, Discrete math., 22, 1, 81-83, (1978) · Zbl 0374.05023
[35] Chang, G.J.; Kuo, D., The \(L(2, 1)\)-labeling problem on graphs, SIAM J. discrete math., 9, 2, 309-316, (1996) · Zbl 0860.05064
[36] Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. math. statist., 23, 493-507, (1952) · Zbl 0048.11804
[37] Chetwynd, A.; Häggkvist, R., An improvement of hind’s upper bound on the total chromatic number, Combin. probab. comput., 5, 2, 99-104, (1996) · Zbl 0862.05039
[38] Chudnovsky, M.; Ovetsky, A., Coloring quasi-line graphs, J. graph theory, 54, 1, 41-50, (2007) · Zbl 1110.05031
[39] M. Chudnovsky, P. Seymour, Perfect matchings in planar cubic graphs (Submitted for publication) · Zbl 1299.05263
[40] Chung, F.R.K.; Graham, R.L.; Frankl, P.; Shearer, J.B., Some intersection theorems for ordered sets and graphs, J. combin. theory ser. A, 43, 1, 23-37, (1986) · Zbl 0655.05001
[41] Descartes, B., A three color problem, Eureka, 9, 21, (1947), Solution in Eureka 10, 1948, URL: http://www.archim.org.uk/eureka/backissues
[42] Díaz, J.; Petit, J.; Serna, M., A guide to concentration bounds, (), 457-507 · Zbl 1048.68060
[43] Diestel, R., Graph theory, (), URL: http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/GraphTheoryIII.pdf · Zbl 0751.05002
[44] Dinur, I.; Friedgut, E.; Regev, O., Independent sets in graph powers are almost contained in juntas, Geom. funct. anal., 18, 77-97, (2008) · Zbl 1147.05058
[45] Edmonds, J., Paths, trees, and flowers, Canad. J. math., 17, 449-467, (1965) · Zbl 0132.20903
[46] Edmonds, J.; Lovász, L.; Pulleyblank, W.R., Brick decompositions and the matching rank of graphs, Combinatorica, 2, 3, 247-274, (1982) · Zbl 0521.05035
[47] Egorychev, G.P., Proof of the Van der Waerden conjecture for permanents, Sibirsk. mat. zh., 22, 6, (1981), 65-71, 225 · Zbl 0479.15007
[48] Egorychev, G.P., The solution of the Van der Waerden problem for permanents, Dokl. akad. nauk SSSR, 258, 5, 1041-1044, (1981) · Zbl 0508.15004
[49] Egorychev, G.P., The solution of Van der waerden’s problem for permanents, Adv. in math., 42, 3, 299-305, (1981) · Zbl 0478.15003
[50] Erdős, P., Some remarks on the theory of graphs, Bull. amer. math. soc., 53, 292-294, (1947) · Zbl 0032.19203
[51] Erdős, P., Graph theory and probability, Canad. J. math., 11, 34-38, (1959) · Zbl 0084.39602
[52] Erdős, P.; Lovász, L., Problems and results on 3-chromatic hypergraphs and some related questions, (), 609-627
[53] Erdős, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, (), 125-157, Winnipeg, Man., Utilitas Math
[54] Fajtlowicz, S., On the size of independent sets in graphs, (), 269-274, Winnipeg, Man., Utilitas Math
[55] Falikman, D.I., Proof of the Van der Waerden conjecture on the permanent of a doubly stochastic matrix, Mat. zametki, 29, 6, (1981), 931-938, 957 · Zbl 0475.15007
[56] Faudree, R.J.; Gyárfás, A.; Schelp, R.H.; Tuza, Zs., Induced matchings in bipartite graphs, Discrete math., 78, 1-2, 83-87, (1989) · Zbl 0709.05026
[57] Faudree, R.J.; Schelp, R.H.; Gyárfás, A.; Tuza, Zs., The strong chromatic index of graphs, Ars combin., 29, B, 205-211, (1990), Twelfth British Combinatorial Conference (Norwich, 1989) · Zbl 0721.05018
[58] Feige, U.; Kilian, J., Zero knowledge and the chromatic number, J. comput. system sci., 57, 2, 187-199, (1998), Complexity 96—The Eleventh Annual IEEE Conference on Computational Complexity (Philadelphia, PA) · Zbl 0921.68089
[59] Frankl, P.; Rödl, V., Near perfect coverings in graphs and hypergraphs, European J. combin., 6, 4, 317-326, (1985) · Zbl 0624.05055
[60] Friedgut, E., Boolean functions with low average sensitivity depend on few coordinates, Combinatorica, 18, 1, 27-35, (1998) · Zbl 0909.06008
[61] Friedgut, E., Hypergraphs, entropy, and inequalities, Amer. math. monthly, 111, 9, 749-760, (2004) · Zbl 1187.94017
[62] Friedgut, E.; Kalai, G.; Naor, A., Boolean functions whose Fourier transform is concentrated on the first two levels, Adv. in appl. math., 29, 3, 427-437, (2002) · Zbl 1039.91014
[63] Garey, M.R.; Johnson, D.S., The complexity of near-optimal graph coloring, J. assoc. comput. Mach., 23, 1, 43-49, (1976) · Zbl 0322.05111
[64] Garey, M.R.; Johnson, D.S.; Stockmeyer, L., Some simplified \(N P\)-complete problems, (), 47-63
[65] Georges, J.P.; Mauro, D.W.; Whittlesey, M.A., Relating path coverings to vertex labellings with a condition at distance two, Discrete math., 135, 1-3, 103-111, (1994) · Zbl 0811.05058
[66] Ghandehari, M.; Hatami, H., Fourier analysis and large independent sets in powers of complete graphs, J. combin. theory ser. B, 98, 1, 164-172, (2008) · Zbl 1127.05069
[67] Graham, R.L.; Knuth, D.E.; Patashnik, O., Concrete mathematics, (1989), Addison-Wesley Publishing Company Advanced Book Program Reading, MA, A foundation for computer science · Zbl 0668.00003
[68] Greenwell, D.; Lovász, L., Applications of product colouring, Acta math. acad. sci. hungar., 25, 335-340, (1974) · Zbl 0294.05108
[69] Griggs, J.; Murphy, O., Edge density and independence ratio in triangle-free graphs with maximum degree three, Discrete math., 152, 1-3, 157-170, (1996) · Zbl 0856.05056
[70] J.R. Griggs, D. Král’, Graph labellings with variable weights, a survey, Discrete Appl. Math. (in press) · Zbl 1211.05145
[71] Griggs, J.R.; Yeh, R.K., Labelling graphs with a condition at distance 2, SIAM J. discrete math., 5, 4, 586-595, (1992) · Zbl 0767.05080
[72] Grimmett, G.R.; Stirzaker, D.R., Probability and random processes, (2001), Oxford University Press New York · Zbl 1015.60002
[73] Grimmett, G.R.; Welsh, D., Probability: an introduction, ()
[74] Grötzsch, H., Zur theorie der diskreten gebilde. VII. ein dreifarbensatz für dreikreisfreie netze auf der kugel, Wiss. Z. martin-luther-univ. halle-Wittenberg. math.-nat. reihe, 8, 109-120, (1958/1959)
[75] Grünbaum, B., Acyclic colorings of planar graphs, Israel J. math., 14, 390-408, (1973) · Zbl 0265.05103
[76] Gurvits, L., Hyperbolic polynomials approach to Van der Waerden/schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications, (), 417-426 · Zbl 1301.90071
[77] Halldórsson, M.M., A still better performance guarantee for approximate graph coloring, Inform. process. lett., 45, 1, 19-23, (1993) · Zbl 0768.68043
[78] Hartfiel, D.J., A simplified form for nearly reducible and nearly decomposable matrices, Proc. amer. math. soc., 24, 388-393, (1970) · Zbl 0205.04701
[79] Hartfiel, D.J.; Crosby, J.W., On the permanent of a certain class of \((0, 1)\)-matrices, Canad. math. bull., 14, 507-511, (1971) · Zbl 0229.05024
[80] H. Hatami, X. Zhu, The fractional chromatic number of graphs of maximum degree at most three (submitted for publication) · Zbl 1207.05054
[81] F. Havet, R.J. Kang, T. Müller, J.-S. Sereni, Circular choosability (Submitted for publication)
[82] F. Havet, B. Reed, J.-S. Sereni, L(p,1)-labelling of graphs. Manuscript · Zbl 1192.05135
[83] F. Havet, B. Reed, J.-S. Sereni, L(2,1)-labelling of graphs. in: Proceedings of the Nineteenth ACM-SIAM Symposium on Discrete Algorithm, SODA 2008, January 2008, pp. 621-630 · Zbl 1192.05135
[84] F Havet, J. van den Heuvel, C. McDiarmid, B. Reed, List colouring squares of planar graphs. Manuscript · Zbl 1341.05073
[85] Havet, F; van den Heuvel, J.; McDiarmid, C.; Reed, B., List colouring squares of planar graphs, (), 515-519 · Zbl 1341.05073
[86] Heckman, C.C.; Thomas, R., A new proof of the independence ratio of triangle-free cubic graphs, Discrete math., 233, 1-3, 233-237, (2001), Graph theory (Prague, 1998) · Zbl 0982.05071
[87] van den Heuvel, J.; McGuinness, S., Coloring the square of a planar graph, J. graph theory, 42, 2, 110-124, (2003) · Zbl 1008.05065
[88] Hind, H.; Molloy, M.; Reed, B., Total coloring with \(\Delta + \operatorname{poly}(\log \Delta)\) colors, SIAM J. comput., 28, 3, 816-821, (1999), (electronic) · Zbl 0917.05028
[89] Hind, H.R., An upper bound for the total chromatic number, Graphs combin., 6, 2, 153-159, (1990) · Zbl 0725.05043
[90] Hoffman, A.J.; Singleton, R.R., On Moore graphs with diameters 2 and 3, IBM J. res. develop., 4, 497-504, (1960) · Zbl 0096.38102
[91] Holyer, I., The NP-completeness of edge-coloring, SIAM J. comput., 10, 4, 718-720, (1981) · Zbl 0473.68034
[92] P. Horák, The strong chromatic index of graphs with maximum degree four, in: Contemporary methods in graph theory, Bibliographisches Inst., Mannheim, 1990, pp. 399-403
[93] Janson, S.; Łuczak, T.; Ruciński, A., Random graphs, ()
[94] Jensen, T.R.; Toft, B., Graph coloring problems, (), A Wiley-Interscience Publication · Zbl 0971.05046
[95] A.R. Johansson, Asymptotic choice number for triangle free graphs, Technical Report 91-95, DIMACS, 1996
[96] T.K. Jonas, Graph coloring analogues with a condition at distance two: \(L(2, 1)\)-labelings and list \(\lambda\)-labelings, Ph.D. Thesis, University of South Carolina, 1993
[97] Jones, K.F., Size and independence in triangle-free graphs with maximum degree three, J. graph theory, 14, 5, 525-535, (1990) · Zbl 0739.05046
[98] Kahn, J., Coloring nearly-disjoint hypergraphs with \(n + o(n)\) colors, J. combin. theory ser. A, 59, 1, 31-39, (1992) · Zbl 0774.05073
[99] Kahn, J., Asymptotically good List-colorings, J. combin. theory ser. A, 73, 1, 1-59, (1996) · Zbl 0851.05081
[100] Kahn, J., Asymptotics of the chromatic index for multigraphs, J. combin. theory ser. B, 68, 2, 233-254, (1996) · Zbl 0861.05026
[101] Kahn, J., Asymptotics of the List-chromatic index for multigraphs, Random structures algorithms, 17, 2, 117-156, (2000) · Zbl 0956.05038
[102] Kahn, J., An entropy approach to the hard-core model on bipartite graphs, Combin. probab. comput., 10, 3, 219-237, (2001) · Zbl 0985.60088
[103] Kahn, J., Entropy, independent sets and antichains: A new approach to dedekind’s problem, Proc. amer. math. soc., 130, 2, 371-378, (2002), (electronic) · Zbl 0982.05014
[104] Kahn, J.; Kalai, G.; Linial, N., The influence of variables on Boolean functions, (), 68-80
[105] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[106] Kelly, J.B.; Kelly, L.M., Paths and circuits in critical graphs, Amer. J. math., 76, 786-792, (1954) · Zbl 0056.16902
[107] Kim, J.H., On brooks’ theorem for sparse graphs, Combin. probab. comput., 4, 2, 97-132, (1995) · Zbl 0833.05030
[108] A.D. King, B. Reed, Bounding \(\chi\) in terms of \(\omega\) and \(\Delta\) for quasi-line graphs, J. Graph Theory (in press)
[109] King, A.D.; Reed, B.; Vetta, A., An upper bound for the chromatic number of line graphs, European J. combin., 28, 8, 2182-2187, (2007) · Zbl 1125.05039
[110] A.V. Kostochka, Communication to B. Toft
[111] Kostochka, A.V., The total chromatic number of any multigraph with maximum degree five is at most seven, Discrete math., 162, 1-3, 199-214, (1996) · Zbl 0871.05023
[112] Ł. Kowalik, J.-S. Sereni, R. Škrekovski, Total colouring of plane graphs with maximum degree nine, SIAM J. Discrete Math. (in press)
[113] Král’, D., The channel assignment problem with variable weights, SIAM J. discrete math., 20, 3, 690-704, (2006), (electronic) · Zbl 1146.94003
[114] D. Král’, P. Škoda, Bounds for the real number graph labellings and application to labellings of the triangular lattice, SIAM J. Discrete Math. (in press)
[115] Král’, D.; Škrekovski, R., A theorem about the channel assignment problem, SIAM J. discrete math., 16, 3, 426-437, (2003), (electronic) · Zbl 1029.05053
[116] D. Král’, J.-S. Sereni, M. Stiebitz, A new lower bound on the number of perfect matchings in cubic graphs (Submitted for publication) · Zbl 1207.05157
[117] Lawrence, J., Covering the vertex set of a graph with subgraphs of smaller degree, Discrete math., 21, 1, 61-68, (1978) · Zbl 0371.05024
[118] Liu, D.D.-F.; Zhu, X., Multilevel distance labelings for paths and cycles, SIAM J. discrete math., 19, 3, 610-621, (2005), (electronic) · Zbl 1095.05033
[119] Lovász, L., On chromatic number of finite set-systems, Acta math. acad. sci. hungar., 19, 59-67, (1968) · Zbl 0157.55203
[120] Lovász, L., On the Shannon capacity of a graph, IEEE trans. inform. theory, 25, 1, 1-7, (1979) · Zbl 0395.94021
[121] Lovász, L.; Plummer, M.D., Matching theory, (), Annals of Discrete Mathematics, 29 · Zbl 0618.05001
[122] G. Lugosi, Concentration-of-measure inequalities. Lecture notes, URL: http://www.econ.upf.edu/ lugosi/anu.pdf
[123] J. Matoušek, J. Vondrák, The probabilistic method. Lecture notes, URL: http://kam.mff.cuni.cz/ matousek/lectnotes.html
[124] McDiarmid, C., On the method of bounded differences, (), 148-188
[125] McDiarmid, C., Concentration, (), 195-248 · Zbl 0927.60027
[126] McDiarmid, C., Concentration for independent permutations, Combin. probab. comput., 11, 2, 163-178, (2002) · Zbl 1001.60014
[127] McDiarmid, C.; Reed, B., On total colourings of graphs, J. combin. theory ser. B, 57, 1, 122-130, (1993) · Zbl 0725.05036
[128] McEliece, R.J., ()
[129] McEliece, R.J., The theory of information and coding, (), With a foreword by Mark Kac · Zbl 1003.94003
[130] McKay, B.D., Independent sets in regular graphs of high girth, (), 179-185 · Zbl 0644.05028
[131] Minc, H., Upper bounds for permanents of \((0, 1)\)-matrices, Bull. amer. math. soc., 69, 789-791, (1963) · Zbl 0116.25202
[132] Minc, H., On lower bounds for permanents of \((0, 1)\) matrices, Proc. amer. math. soc., 22, 117-123, (1969) · Zbl 0192.36801
[133] B. Mohar, Choosability for the circular chromatic number. Problem of the month, January 2002. http://www.fmf.uni-lj.si/ mohar/
[134] Molloy, M.; Reed, B., A bound on the strong chromatic index of a graph, J. combin. theory ser. B, 69, 2, 103-109, (1997) · Zbl 0880.05036
[135] Molloy, M.; Reed, B., A bound on the total chromatic number, Combinatorica, 18, 2, 241-280, (1998) · Zbl 0921.05033
[136] Molloy, M.; Reed, B., Colouring graphs where chromatic number is almost their maximum degree, (), 216-225 · Zbl 0918.05053
[137] Molloy, M.; Reed, B., Further algorithmic aspects of the local lemma, (), 524-529 · Zbl 1028.68105
[138] M. Molloy, B. Reed, Near-optimal list colorings. in: Proceedings of the Ninth International Conference Random Structures and Algorithms (Poznan, 1999), vol. 17, 2000, pp. 376-402 · Zbl 0971.05047
[139] Molloy, M.; Reed, B., Colouring graphs when the number of colours is nearly the maximum degree, (), 462-470, (electronic) · Zbl 1323.05052
[140] Molloy, M.; Reed, B., Graph colouring and the probabilistic method, () · Zbl 0926.05018
[141] E. Mossel, R. O’Donnell, K. Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality (extended abstract), in: Proc. Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, October 2005, pp. 21-30
[142] T. Müller, R. Waters, Circular choosability is always rational (Submitted for publication)
[143] Müller, V., On colorable critical and uniquely colorable critical graphs, (), 385-386 · Zbl 0329.05105
[144] Müller, V., On colorings of graphs without short cycles, Discrete math., 26, 2, 165-176, (1979) · Zbl 0407.05037
[145] Muthu, R.; Narayanan, N.; Subramanian, C.R., Improved bounds on acyclic edge colouring, Discrete math., 307, 23, 3063-3069, (2007) · Zbl 1128.05022
[146] Mycielski, J., Sur le coloriage des graphs, Colloq. math., 3, 161-162, (1955), URL: http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf · Zbl 0064.17805
[147] Naddef, D., Rank of maximum matchings in a graph, Math. programming, 22, 1, 52-70, (1982) · Zbl 0468.90052
[148] Nešetril, J., \(K\)-chromatic graphs without cycles of length \(\leq 7\), Comment. math. univ. carolinae, 7, 373-376, (1966)
[149] Nešetřil, J., On uniquely colorable graphs without short cycles, Časopis Pěst. mat., 98, (1973), 122-125, 212 · Zbl 0257.05107
[150] Nešetřil, J.; Rödl, V., A short proof of the existence of highly chromatic hypergraphs without short cycles, J. combin. theory ser. B, 27, 2, 225-227, (1979) · Zbl 0413.05039
[151] Nešetřil, J.; Wormald, N.C., The acyclic edge chromatic number of a random \(d\)-regular graph is \(d + 1\), J. graph theory, 49, 1, 69-74, (2005) · Zbl 1062.05062
[152] Norine, S., On two questions about circular choosability, J. graph theory, 58, 3, 261-269, (2008) · Zbl 1189.05062
[153] Pippenger, N.; Spencer, J., Asymptotic behavior of the chromatic index for hypergraphs, J. combin. theory ser. A, 51, 1, 24-42, (1989) · Zbl 0729.05038
[154] Rabern, L., A note on reed’s conjecture, SIAM J. discrete math., 22, 2, 820-827, (2008) · Zbl 1191.05042
[155] Radhakrishnan, J., An entropy proof of bregman’s theorem, J. combin. theory ser. A, 77, 1, 161-164, (1997) · Zbl 0894.15007
[156] Radhakrishnan, J., Entropy and counting, ()
[157] Reed, B., \(\omega, \Delta\), and \(\chi\), J. graph theory, 27, 4, 177-212, (1998) · Zbl 0980.05026
[158] Reed, B.; Sudakov, B., List colouring of graphs with at most \((2 - o(1)) \chi\) vertices, (), 587-603 · Zbl 0997.05031
[159] Reed, B.; Sudakov, B., List colouring when the chromatic number is close to the order of the graph, Combinatorica, 25, 1, 117-123, (2005) · Zbl 1063.05049
[160] Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R., The four-colour theorem, J. combin. theory ser. B, 70, 1, 2-44, (1997) · Zbl 0883.05056
[161] Rödl, V., On a packing and covering problem, European J. combin., 6, 1, 69-78, (1985) · Zbl 0565.05016
[162] Rosenfeld, M., On the total coloring of certain graphs, Israel J. math., 9, 396-402, (1971) · Zbl 0211.56604
[163] Sanders, D.P.; Zhao, Y., On total 9-coloring planar graphs of maximum degree seven, J. graph theory, 31, 1, 67-73, (1999) · Zbl 0922.05025
[164] Sanders, D.P.; Zhao, Y., Planar graphs of maximum degree seven are class I, J. combin. theory ser. B, 83, 2, 201-212, (2001) · Zbl 1024.05031
[165] Scheinerman, E.R.; Ullman, D.H., Fractional graph theory, (), A rational approach to the theory of graphs, With a foreword by Claude Berge, A Wiley-Interscience Publication
[166] Schrijver, A., A short proof of minc’s conjecture, J. combin. theory ser. A, 25, 1, 80-83, (1978) · Zbl 0391.15006
[167] Schrijver, A., Counting 1-factors in regular bipartite graphs, J. combin. theory ser. B, 72, 1, 122-135, (1998) · Zbl 0905.05060
[168] Schrijver, A.; Valiant, W.G., On lower bounds for permanents, Ned. akad. wetensch. indag. math., 42, 4, 425-427, (1980) · Zbl 0451.15009
[169] Simonyi, G., Graph entropy: A survey, (), 399-441 · Zbl 0828.05001
[170] Simonyi, G., Perfect graphs and graph entropy. an updated survey, (), 293-328 · Zbl 0990.05054
[171] Sinkhorn, R., Concerning a conjecture of Marshall Hall, Proc. amer. math. soc., 21, 197-201, (1969) · Zbl 0172.03802
[172] Spencer, J., Nine lectures on random graphs, (), 293-347, URL: http://cs.nyu.edu/spencer/papers/french.pdf · Zbl 0792.05130
[173] Spencer, J., Modern probabilistic methods in combinatorics, (), 215-231 · Zbl 0826.60006
[174] Spencer, J., The Erdős existence argument, (), 337-344, URL: http://cs.nyu.edu/spencer/papers/erdosex.pdf · Zbl 0867.05061
[175] Srinivasan, A., Improved algorithmic versions of the lovász local lemma, (), 611-620 · Zbl 1192.68837
[176] Staton, W., Some Ramsey-type numbers and the independence ratio, Trans. amer. math. soc., 256, 353-370, (1979) · Zbl 0428.05028
[177] Szele, T., Kombinatorische untersuchungen über den gerichteten vollständigen graphen, Mat. fiz. lapok, 50, 223-256, (1943) · Zbl 0061.41309
[178] Talagrand, M., Concentration of measure and isoperimetric inequalities in product spaces, Inst. hautes études sci. publ. math., 81, 73-205, (1995) · Zbl 0864.60013
[179] Terras, A., Fourier analysis on finite groups and applications, () · Zbl 0928.43001
[180] R. Thomas, The four colour theorem. URL: http://www.math.gatech.edu/ thomas/FC/fourcolor.html · Zbl 0883.05056
[181] Thomassen, C., Color-critical graphs on a fixed surface, J. combin. theory ser. B, 70, 1, 67-100, (1997) · Zbl 0883.05051
[182] Thue, A., Über unendliche zeichenreihen, Norske vid. selsk. skr. I mat. nat. kl., 7, 1-22, (1906) · JFM 39.0283.01
[183] A. Thue, Trygve Nagell, Atle Selberg, Sigmund Selberg, and Knut Thalberg (Eds.) Selected Mathematical Papers, Universitetsforlaget, Oslo, 1977. With an introduction by Carl Ludwig Siegel and a biography by Viggo Brun · Zbl 0378.92010
[184] Tutte, W.T., A contribution to the theory of chromatic polynomials, Canad. J. math., 6, 80-91, (1954) · Zbl 0055.17101
[185] Ungar, P.; Descartes, B., Advanced problems and solutions: solutions: 4526, Amer. math. monthly, 61, 5, 352-353, (1954)
[186] Vijayaditya, N., On total chromatic number of a graph, J. London math. soc., 2, 3, 405-408, (1971) · Zbl 0223.05103
[187] Vince, A., Star chromatic number, J. graph theory, 12, 4, 551-559, (1988) · Zbl 0658.05028
[188] Vizing, V.G., On an estimate of the chromatic class of a \(p\)-graph, Diskretn. anal. no., 3, 25-30, (1964)
[189] Vizing, V.G., Critical graphs with given chromatic class, Diskretn. anal. no., 5, 9-17, (1965)
[190] Vizing, V.G., Some unsolved problems in graph theory, Uspekhi mat. nauk, 23, 6 (144), 117-134, (1968) · Zbl 0177.52301
[191] Voorhoeve, M., A lower bound for the permanents of certain \((0, 1)\)-matrices, Nede. akad. wetensch. indag. math., 41, 1, 83-86, (1979) · Zbl 0401.05005
[192] van der Waerden, B.L., Aufgabe 45, Jber. Deutsch. math. verein., 35, 117, (1926)
[193] Wang, W., Total chromatic number of planar graphs with maximum degree ten, J. graph theory, 54, 2, 91-102, (2006) · Zbl 1110.05037
[194] Yap, H.P., Total colourings of graphs, () · Zbl 0636.05025
[195] Yeh, R.K., A survey on labeling graphs with a condition at distance two, Discrete math., 306, 12, 1217-1231, (2006) · Zbl 1094.05047
[196] Zhu, X., Circular chromatic number: A survey, Discrete math., 229, 1-3, 371-410, (2001), Combinatorics, graph theory, algorithms and applications · Zbl 0973.05030
[197] Zhu, X., Circular choosability of graphs, J. graph theory, 48, 3, 210-218, (2005) · Zbl 1065.05044
[198] Zykov, A.A., On some properties of linear complexes, Mat. sbornik N.S., 24, 66, 163-188, (1949), English translation in Amer. Math. Soc. Transl. 79 (1952) (in Russian)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.