Fractional coloring with local demands and applications to degree-sequence bounds on the independence number. (English) Zbl 07923452
Summary: In a fractional coloring, vertices of a graph are assigned measurable subsets of the real line and adjacent vertices receive disjoint subsets; the fractional chromatic number of a graph is at most \(k\) if it has a fractional coloring in which each vertex receives a subset of \([0, 1]\) of measure at least \(1 / k\). We introduce and develop the theory of “fractional colorings with local demands” wherein each vertex “demands” a certain amount of color that is determined by local parameters such as its degree or the clique number of its neighborhood. This framework provides the natural setting in which to generalize degree-sequence type bounds on the independence number. Indeed, by Linear Programming Duality, all of the problems we study have an equivalent formulation as a problem concerning weighted independence numbers, and they often imply new bounds on the independence number.
Our results and conjectures are inspired by many of the most classical results and important open problems concerning the independence number and the chromatic number, often simultaneously. We conjecture a local strengthening of both Shearer’s bound on the independence number of triangle-free graphs and the fractional relaxation of Molloy’s recent bound on their chromatic number [M. Molloy, ibid. 134, 264–284 (2019; Zbl 1402.05076)], as well as a longstanding problem of M. Ajtai et al. [J. Comb. Theory, Ser. A 29, 354–360 (1980; Zbl 0455.05045)] on the independence number of \(K_r\)-free graphs and the fractional relaxations of Reed’s \(\omega\), \(\Delta\), \(\chi\) Conjecture [B. Reed, J. Graph Theory 27, No. 4, 177–212 (1998; Zbl 0980.05026)] and the Total Coloring Conjecture. We prove an approximate version of the first two, and we prove “local demands” versions of Vizing’s Theorem and of some \(\chi \)-boundedness results.
Our results and conjectures are inspired by many of the most classical results and important open problems concerning the independence number and the chromatic number, often simultaneously. We conjecture a local strengthening of both Shearer’s bound on the independence number of triangle-free graphs and the fractional relaxation of Molloy’s recent bound on their chromatic number [M. Molloy, ibid. 134, 264–284 (2019; Zbl 1402.05076)], as well as a longstanding problem of M. Ajtai et al. [J. Comb. Theory, Ser. A 29, 354–360 (1980; Zbl 0455.05045)] on the independence number of \(K_r\)-free graphs and the fractional relaxations of Reed’s \(\omega\), \(\Delta\), \(\chi\) Conjecture [B. Reed, J. Graph Theory 27, No. 4, 177–212 (1998; Zbl 0980.05026)] and the Total Coloring Conjecture. We prove an approximate version of the first two, and we prove “local demands” versions of Vizing’s Theorem and of some \(\chi \)-boundedness results.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 90C05 | Linear programming |
Keywords:
graph coloring; fractional coloring; independence number; clique number; degree-sequence; local demands; triangle-free; Reed’s conjecture; edge coloring; list coloringReferences:
| [1] | Ajtai, M.; Erdős, P.; Komlós, J.; Szemerédi, E., On Turán’s theorem for sparse graphs, Combinatorica, 1, 4, 313-317, 1981 · Zbl 0491.05038 |
| [2] | Ajtai, M.; Komlós, J.; Szemerédi, E., A note on Ramsey numbers, J. Comb. Theory, Ser. A, 29, 3, 354-360, 1980 · Zbl 0455.05045 |
| [3] | Alon, N.; Spencer, J. H., The Probabilistic Method, Wiley-Interscience Series in Discrete Mathematics and Optimization, 2000, Wiley-Interscience [John Wiley & Sons]: Wiley-Interscience [John Wiley & Sons] New York, With an appendix on the life and work of Paul Erdős · Zbl 0996.05001 |
| [4] | Alon, N.; Tuza, Z.; Voigt, M., Choosability and fractional chromatic numbers, Graphs and Combinatorics. Graphs and Combinatorics, Marseille, 1995. Graphs and Combinatorics. Graphs and Combinatorics, Marseille, 1995, Discrete Math., 165/166, 31-38, 1997 · Zbl 0877.05020 |
| [5] | Appel, K.; Haken, W., Every planar map is four colorable, Bull. Am. Math. Soc., 82, 5, 711-712, 1976 · Zbl 0331.05106 |
| [6] | Asplund, E.; Grünbaum, B., On a coloring problem, Math. Scand., 8, 181-188, 1960 · Zbl 0095.17002 |
| [7] | Behzad, M., Graphs and their chromatic numbers, 1965, Michigan State University, ProQuest LLC, Ann Arbor, MI, Thesis (Ph.D.) |
| [8] | Bohman, T.; Holzman, R., On a list coloring conjecture of Reed, J. Graph Theory, 41, 2, 106-109, 2002 · Zbl 1012.05070 |
| [9] | Bohman, T.; Keevash, P., Dynamic concentration of the triangle-free process, Random Struct. Algorithms, 58, 2, 221-293, 2021 · Zbl 1522.05287 |
| [10] | Bollobás, B., The independence ratio of regular graphs, Proc. Am. Math. Soc., 83, 2, 433-436, 1981 · Zbl 0474.05057 |
| [11] | Bonamy, M.; Kelly, T.; Nelson, P.; Postle, L., Bounding χ by a fraction of Δ for graphs without large cliques, J. Comb. Theory, Ser. B, 157, 263-282, 2022 · Zbl 1497.05068 |
| [12] | 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. Comb. Theory, Ser. B, 23, 2-3, 247-250, 1977 · Zbl 0336.05104 |
| [13] | Brause, C.; Randerath, B.; Rautenbach, D.; Schiermeyer, I., A lower bound on the independence number of a graph in terms of degrees and local clique sizes, Discrete Appl. Math., 209, 59-67, 2016 · Zbl 1339.05279 |
| [14] | Brooks, R. L., On colouring the nodes of a network, Proc. Camb. Philos. Soc., 37, 194-197, 1941 · Zbl 0027.26403 |
| [15] | Cames van Batenburg, W.; de Joannis de Verclos, R.; Kang, R. J.; Pirot, F., Bipartite induced density in triangle-free graphs, Electron. J. Comb., 27, 2, Article 2.34 pp., 2020 · Zbl 1441.05119 |
| [16] | Caro, Y., New results on the independence number, 1979, Tel Aviv University, Technical report |
| [17] | Caro, Y.; Tuza, Z., Improved lower bounds on k-independence, J. Graph Theory, 15, 1, 99-107, 1991 · Zbl 0753.68079 |
| [18] | Chudnovsky, M.; Ovetsky, A., Coloring quasi-line graphs, J. Graph Theory, 54, 1, 41-50, 2007 · Zbl 1110.05031 |
| [19] | Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R., The strong perfect graph theorem, Ann. Math. (2), 164, 1, 51-229, 2006 · Zbl 1112.05042 |
| [20] | Chudnovsky, M.; Scott, A.; Seymour, P., Induced subgraphs of graphs with large chromatic number. III. Long holes, Combinatorica, 37, 6, 1057-1072, 2017 · Zbl 1399.05068 |
| [21] | Chudnovsky, M.; Scott, A.; Seymour, P.; Spirkl, S., Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes, J. Comb. Theory, Ser. B, 140, 84-97, 2020 · Zbl 1430.05034 |
| [22] | Chudnovsky, M.; Seymour, P., Claw-free graphs VI. Colouring, J. Comb. Theory, Ser. B, 100, 6, 560-572, 2010 · Zbl 1207.05050 |
| [23] | Davies, E.; de Joannis de Verclos, R.; Kang, R. J.; Pirot, F., Coloring triangle-free graphs with local list sizes, Random Struct. Algorithms, 57, 3, 730-744, 2020 · Zbl 1464.05148 |
| [24] | Descartes, B., Solution to advanced problem no. 4526, Am. Math. Mon., 61, 532, 1954 |
| [25] | Dvořák, Z.; Hu, X., Planar graphs without cycles of length 4 or 5 are \((11 : 3)\)-colorable, Eur. J. Comb., 82, Article 102996 pp., 2019 · Zbl 1419.05054 |
| [26] | Dvořák, Z.; Hu, X.; Sereni, J.-S., A 4-choosable graph that is not \((8 : 2)\)-choosable, Adv. Comb., 5, 2019, 9 · Zbl 1450.05074 |
| [27] | Dvořák, Z.; Mnich, M., Large independent sets in triangle-free planar graphs, SIAM J. Discrete Math., 31, 2, 1355-1373, 2017 · Zbl 1371.68111 |
| [28] | Dvořák, Z.; Sereni, J.-S.; Volec, J., Subcubic triangle-free graphs have fractional chromatic number at most 14/5, J. Lond. Math. Soc. (2), 89, 3, 641-662, 2014 · Zbl 1295.05103 |
| [29] | Dvořák, Z.; Sereni, J.-S.; Volec, J., Fractional coloring of triangle-free planar graphs, Electron. J. Comb., 22, 4, Article 4.11 pp., 2015 · Zbl 1323.05045 |
| [30] | Edmonds, J., Maximum matching and a polyhedron with \(0, 1\)-vertices, J. Res. Natl. Bur. Stand. B, 69, 125-130, 1965 · Zbl 0141.21802 |
| [31] | Edwards, K.; King, A. D., Bounding the fractional chromatic number of \(K_{\operatorname{\Delta}} \)-free graphs, SIAM J. Discrete Math., 27, 2, 1184-1208, 2013 · Zbl 1272.05046 |
| [32] | Erdős, P., Graph theory and probability, Can. J. Math., 11, 34-38, 1959 · Zbl 0084.39602 |
| [33] | Erdős, P.; Rubin, A. L.; Taylor, H., Choosability in graphs, (Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979) Congress. Numer., XXVI, 1980, Utilitas Math: Utilitas Math Winnipeg, Man), 125-157 · Zbl 0469.05032 |
| [34] | Esperet, L.; Kang, R. J.; Thomassé, S., Separation choosability and dense bipartite induced subgraphs, Comb. Probab. Comput., 28, 5, 720-732, 2019 · Zbl 1436.05036 |
| [35] | Fajtlowicz, S., On the size of independent sets in graphs, (Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978) Congress. Numer., XXI, 1978, Utilitas Math: Utilitas Math Winnipeg, Man), 269-274 · Zbl 0434.05044 |
| [36] | Fajtlowicz, S., Independence, clique size and maximum degree, Combinatorica, 4, 1, 35-38, 1984 · Zbl 0576.05025 |
| [37] | Farzad, B.; Molloy, M.; Reed, B., (Delta-k)-critical graphs, J. Comb. Theory, Ser. B, 93, 2, 173-185, 2005 · Zbl 1062.05056 |
| [38] | Fiz Pontiveros, G.; Griffiths, S.; Morris, R., The triangle-free process and the Ramsey number \(R(3, k)\), Mem. Am. Math. Soc., 263, 1274, 2020, v+125 · Zbl 1439.05001 |
| [39] | Griggs, J. R., Lower bounds on the independence number in terms of the degrees, J. Comb. Theory, Ser. B, 34, 1, 22-39, 1983 · Zbl 0505.05037 |
| [40] | Gyárfás, A., On Ramsey covering-numbers, (Infinite and Finite Sets (Colloq., Keszthely, 1973; Dedicated to P. Erdős on His 60th Birthday), vol. II. Infinite and Finite Sets (Colloq., Keszthely, 1973; Dedicated to P. Erdős on His 60th Birthday), vol. II, Colloq. Math. Soc. Janós Bolyai, vol. 10, 1975, North-Holland: North-Holland Amsterdam), 801-816 · Zbl 0307.05111 |
| [41] | Gyárfás, A., Problems from the world surrounding perfect graphs, (Proceedings of the International Conference on Combinatorial Analysis and Its Applications. Proceedings of the International Conference on Combinatorial Analysis and Its Applications, Pokrzywna, 1985, vol. 19, 1987), 413-441 · Zbl 0718.05041 |
| [42] | Hadwiger, H., Über eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zürich, 88, 133-142, 1943 · Zbl 0061.41308 |
| [43] | Harant, J.; Mohr, S., On Selkow’s bound on the independence number of graphs, Discuss. Math., Graph Theory, 39, 3, 655-657, 2019 · Zbl 1411.05202 |
| [44] | Harant, J.; Rautenbach, D., Independence in connected graphs, Discrete Appl. Math., 159, 1, 79-86, 2011 · Zbl 1208.05098 |
| [45] | Harant, J.; Schiermeyer, I., On the independence number of a graph in terms of order and size, Discrete Math., 232, 1-3, 131-138, 2001 · Zbl 1030.05091 |
| [46] | Harant, J.; Schiermeyer, I., A lower bound on the independence number of a graph in terms of degrees, Discuss. Math., Graph Theory, 26, 3, 431-437, 2006 · Zbl 1138.05051 |
| [47] | Harris, D. G., Some results on chromatic number as a function of triangle count, SIAM J. Discrete Math., 33, 1, 546-563, 2019 · Zbl 1407.05093 |
| [48] | 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 · Zbl 0982.05071 |
| [49] | Heckman, C. C.; Thomas, R., Independent sets in triangle-free cubic planar graphs, J. Comb. Theory, Ser. B, 96, 2, 253-275, 2006 · Zbl 1087.05044 |
| [50] | Hilton, A. J.W.; Rado, R.; Scott, S. H., A (<5)-colour theorem for planar graphs, Bull. Lond. Math. Soc., 5, 302-306, 1973 · Zbl 0278.05103 |
| [51] | A. Johansson, Asymptotic choice number for triangle free graphs, 1996, Unpublished Manuscript. |
| [52] | A. Johansson, The choice number of sparse graphs, 1996, Unpublished Manuscript. |
| [53] | Kaiser, T.; King, A.; Kráľ, D., Fractional total colourings of graphs of high girth, J. Comb. Theory, Ser. B, 101, 6, 383-402, 2011 · Zbl 1234.05091 |
| [54] | Kardoš, F.; Král’, D.; Sereni, J.-S., The last fraction of a fractional conjecture, SIAM J. Discrete Math., 24, 2, 699-707, 2010 · Zbl 1213.05090 |
| [55] | T. Kelly, L. Postle, The local fractional Brooks’ Theorem, submitted for publication. |
| [56] | Kelly, T.; Postle, L., Improving the Caro-Wei bound and applications to Turán stability, Discrete Appl. Math., 358, 33-43, 2024 · Zbl 07919051 |
| [57] | Kilakos, K.; Reed, B., Fractionally colouring total graphs, Combinatorica, 13, 4, 435-440, 1993 · Zbl 0795.05056 |
| [58] | Kim, J. H., On Brooks’ theorem for sparse graphs, Comb. Probab. Comput., 4, 2, 97-132, 1995 · Zbl 0833.05030 |
| [59] | Kim, J. H., The Ramsey number \(R(3, t)\) has order of magnitude \(t^2 / \log t\), Random Struct. Algorithms, 7, 3, 173-207, 1995 · Zbl 0832.05084 |
| [60] | Kostochka, A. V.; Nešetřil, J., Properties of Descartes’ construction of triangle-free graphs with high chromatic number, Comb. Probab. Comput., 8, 5, 467-472, 1999 · Zbl 0951.05036 |
| [61] | Molloy, M., The list chromatic number of graphs with small clique number, J. Comb. Theory, Ser. B, 134, 264-284, 2019 · Zbl 1402.05076 |
| [62] | Molloy, M.; Reed, B., Graph Colouring and the Probabilistic Method, Algorithms and Combinatorics, vol. 23, 2002, Springer-Verlag: Springer-Verlag Berlin · Zbl 0987.05002 |
| [63] | Molloy, M.; Reed, B., Colouring graphs when the number of colours is almost the maximum degree, J. Comb. Theory, Ser. B, 109, 134-195, 2014 · Zbl 1301.05130 |
| [64] | Pettie, S.; Su, H.-H., Distributed coloring algorithms for triangle-free graphs, Inf. Comput., 243(C), 263-280, Aug. 2015 · Zbl 1327.68330 |
| [65] | Reed, B., \( \omega, \operatorname{\Delta} \), and χ, J. Graph Theory, 27, 4, 177-212, 1998 · Zbl 0980.05026 |
| [66] | Reed, B., A strengthening of Brooks’ theorem, J. Comb. Theory, Ser. B, 76, 2, 136-149, 1999 · Zbl 0935.05045 |
| [67] | Reed, B. A., The list colouring constants, J. Graph Theory, 31, 2, 149-153, 1999 · Zbl 0926.05019 |
| [68] | Reed, B. A.; Seymour, P. D., Fractional colouring and Hadwiger’s conjecture, J. Comb. Theory, Ser. B, 74, 2, 147-152, 1998 · Zbl 1029.05060 |
| [69] | Reed, B. A.; Sudakov, B., Asymptotically the list colouring constants are 1, J. Comb. Theory, Ser. B, 86, 1, 27-37, 2002 · Zbl 1030.05043 |
| [70] | Sakai, S.; Togasaki, M.; Yamazaki, K., A note on greedy algorithms for the maximum weighted independent set problem, Discrete Appl. Math., 126, 2-3, 313-322, 2003 · Zbl 1013.90108 |
| [71] | Scheinerman, E. R.; Ullman, D. H., A Rational Approach to the Theory of Graphs, Fractional Graph Theory, 2011, Dover Publications, Inc.: Dover Publications, Inc. Mineola, NY, With a foreword by Claude Berge, Reprint of the 1997 original |
| [72] | Scott, A.; Seymour, P., Induced subgraphs of graphs with large chromatic number. I. Odd holes, J. Comb. Theory, Ser. B, 121, 68-84, 2016 · Zbl 1412.05076 |
| [73] | Scott, A.; Seymour, P., Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue, Combinatorica, 39, 5, 1105-1132, 2019 · Zbl 1449.05110 |
| [74] | Scott, A.; Seymour, P., A survey of χ-boundedness, J. Graph Theory, 95, 3, 473-504, 2020 · Zbl 1486.05102 |
| [75] | Selkow, S. M., A probabilistic lower bound on the independence number of graphs, Discrete Math., 132, 1-3, 363-365, 1994 · Zbl 0810.05039 |
| [76] | Shannon, C. E., A theorem on coloring the lines of a network, J. Math. Phys., 28, 148-151, 1949 · Zbl 0032.43203 |
| [77] | Shearer, J. B., A note on the independence number of triangle-free graphs, Discrete Math., 46, 1, 83-87, 1983 · Zbl 0516.05053 |
| [78] | Shearer, J. B., A note on the independence number of triangle-free graphs. II, J. Comb. Theory, Ser. B, 53, 2, 300-307, 1991 · Zbl 0753.05074 |
| [79] | Shearer, J. B., On the independence number of sparse graphs, Random Struct. Algorithms, 7, 3, 269-271, 1995 · Zbl 0834.05030 |
| [80] | Spencer, J., Asymptotic lower bounds for Ramsey functions, Discrete Math., 20, 1, 69-76, 1977/1978 · Zbl 0375.05033 |
| [81] | Staton, W., Some Ramsey-type numbers and the independence ratio, Trans. Am. Math. Soc., 256, 353-370, 1979 · Zbl 0428.05028 |
| [82] | Sumner, D. P., Subtrees of a graph and the chromatic number, (The Theory and Applications of Graphs. The Theory and Applications of Graphs, Kalamazoo, Mich., 1980, 1981, Wiley: Wiley New York), 557-576 · Zbl 0476.05037 |
| [83] | Thiele, T., A lower bound on the independence number of arbitrary hypergraphs, J. Graph Theory, 30, 3, 213-221, 1999 · Zbl 0926.05022 |
| [84] | Turán, P., Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok, 48, 436-452, 1941 · JFM 67.0732.03 |
| [85] | Vizing, V. G., On an estimate of the chromatic class of a p-graph, Diskretn. Anal., 3, 25-30, 1964 · Zbl 1539.05042 |
| [86] | Vizing, V. G., Some unsolved problems in graph theory, Usp. Mat. Nauk. Usp. Mat. Nauk, Russ. Math. Surv., 23, 6, 125-141, 1968, English translation in · Zbl 0192.60502 |
| [87] | Vizing, V. G., Coloring the vertices of a graph in prescribed colors, Diskretn. Anal., 29, 101, 3-10, 1976 · Zbl 0362.05060 |
| [88] | Wei, V. K., A lower bound on the stability number of a simple graph, 1981, Bell Laboratories, Technical Memorandum 81-11217-9 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
