Subcubic triangle-free graphs have fractional chromatic number at most \(14/5\). (English) Zbl 1295.05103
Summary: We prove that every subcubic triangle-free graph has fractional chromatic number at most \(14/5\), thus confirming a conjecture of C. C. Heckman and R. Thomas [Discrete Math. 233, No. 1–3, 233–237 (2001; Zbl 0982.05071)].
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C72 | Fractional graph theory, fuzzy graph theory |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
Keywords:
Erdős-Vizing conjectureCitations:
Zbl 0982.05071References:
| [1] | M.Albertson, ‘A lower bound for the independence number of a planar graph’, J. Combin. Theory Ser. B, 20 (1976) 84-93. · Zbl 0286.05105 |
| [2] | M.Albertson, B.Bollobás, S.Tucker, ‘The independence ratio and maximum degree of a graph’, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Math. (1976) 43-50. Congressus Numerantium, No. XVII. · Zbl 0344.05156 |
| [3] | K.Appel, W.Haken, ‘Every planar map is four colorable. I. Discharging’, Illinois J. Math., 21 (1977) 429-490. · Zbl 0387.05009 |
| [4] | K.Appel, W.Haken, Every planar map is four colorable, Contemporary Mathematics 98 (American Mathematical Society, Providence, 1989). With the collaboration of J. Koch. · Zbl 0681.05027 |
| [5] | K.Appel, W.Haken, J.Koch, ‘Every planar map is four colorable. II. Reducibility’, Illinois J. Math., 21 (1977) 491-567. · Zbl 0387.05010 |
| [6] | S.Fajtlowicz, ‘On the size of independent sets in graphs’, Congr. Numer., 21 (1978) 269-274. · Zbl 0434.05044 |
| [7] | D.Ferguson, T.Kaiser, D.Král’, ‘The fractional chromatic number of triangle‐free subcubic graphs’, European J. Combin., Preprint, 2012, arXiv:1203.1308. |
| [8] | H.Grötzsch, ‘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 (1958/1959), 109-120. |
| [9] | H.Hatami, X.Zhu, ‘The fractional chromatic number of graphs of maximum degree at most three’, SIAM J. Discrete Math., 23 (2009) 1162-1175. |
| [10] | C. C.Heckman, R.Thomas, ‘A new proof of the independence ratio of triangle‐free cubic graphs’, Discrete Math., 233 (2001) 233-237. · Zbl 0982.05071 |
| [11] | C. C.Heckman, R.Thomas, ‘Independent sets in triangle‐free cubic planar graphs’, J. Combin. Theory Ser. B, 96 (2006) 253-275. · Zbl 1087.05044 |
| [12] | A. J. W.Hilton, R.Rado, S. H.Scott, ‘A (<5)‐colour theorem for planar graphs’, Bull. London Math. Soc., 5 (1973) 302-306. · Zbl 0278.05103 |
| [13] | K. F.Jones, ‘Independence in graphs with maximum degree four’, J. Combin. Theory Ser. B, 37 (1984) 254-269. · Zbl 0547.05057 |
| [14] | K. F.Jones, ‘Size and independence in triangle‐free graphs with maximum degree three’, J. Graph Theory, 14 (1990) 525-535. · Zbl 0739.05046 |
| [15] | M.Larsen, J.Propp, D.Ullman, ‘The fractional chromatic number of Mycielski’s graphs’, J. Graph Theory, 19 (1995) 411-416. · Zbl 0830.05027 |
| [16] | C.‐H.Liu, ‘An upper bound on the fractional chromatic number of triangle‐free subcubic graphs’, submitted for publication. Preprint, 2012, arXiv:1211.4229. |
| [17] | L.Lu, X.Peng, ‘The fractional chromatic number of triangle‐free graphs with \(\operatorname{\Delta} \leqslant 3\)’, Discrete Math., 312 (2012) 3502-3516. · Zbl 1259.05064 |
| [18] | N.Robertson, D. P.Sanders, P.Seymour, R.Thomas, ‘The four‐colour theorem’, J. Combin. Theory Ser. B, 70 (1997) 2-44. · Zbl 0883.05056 |
| [19] | E. R.Scheinerman, D. H.Ullman, Fractional graph theory (Wiley, New York, 1997). · Zbl 0891.05003 |
| [20] | W.Staton, ‘Some Ramsey‐type numbers and the independence ratio’, Trans. Amer. Math. Soc., 256 (1979) 353-370. · Zbl 0428.05028 |
| [21] | R.Steinberg, C.Tovey, ‘Planar Ramsey numbers’, J. Combin. Theory Ser. B, 59 (1993) 288-296. · Zbl 0794.05091 |
| [22] | Z.Tuza, M.Voigt, ‘Every 2‐choosable graph is \(( 2 m , m )\)‐choosable’, J. Graph Theory, 22 (1996) 245-252. · Zbl 0853.05034 |
| [23] | X.Zhu, ‘Bipartite subgraphs of triangle‐free subcubic graphs’, J. Combin. Theory Ser. B, 99 (2009) 62-83. · Zbl 1185.05084 |
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.
