Abstract
A Steinberg-type conjecture on circular coloring is recently proposed that for any prime p ≥ 5, every planar graph of girth p without cycles of length from p + 1 to p(p − 2) is Cp-colorable (that is, it admits a homomorphism to the odd cycle Cp). The assumption of p ≥ 5 being prime number is necessary, and this conjecture implies a special case of Jaeger’s Conjecture that every planar graph of girth 2p — 2 is Cp-colorable for prime p ≥ 5. In this paper, combining our previous results, we show the fractional coloring version of this conjecture is true. Particularly, the p = 5 case of our fractional coloring result shows that every planar graph of girth 5 without cycles of length from 6 to 15 admits a homomorphism to the Petersen graph.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Borodin, O. V., Glebov, A. N., Raspaud, A., et al.: Planar graphs without cycles of length from 4 to 7 are 3-colorable. J. Combin. Theory Ser. B, 93, 303–311 (2005)
Borodin, O. V., Kim, S.-J., Kostochka, A. V., et al.: Homomorphisms from sparse graphs with large girth. J. Combin. Theory Ser. B, 90, 147–159 (2004)
Cohen-Addad, V., Hebdige, M., Král’, D., et al.: Steinberg’s conjecture is false. J. Combin. Theory Ser. B, 122, 452–456 (2017)
Cranston, D., Li, J.: Circular flows in planar graphs. SIAM J. Discrete Math., 34, 497–519 (2020)
Dvořák, Z., Postle, L.: Density of 5/2-critical graphs. Combinatorica, 37, 863–886 (2017)
Dvořák, Z., Škrekovski, R., Valla, T.: Planar graphs of odd-girth at least 9 are homomorphic to the Petersen graph. SIAM J. Discrete Math., 22, 568–591 (2008)
Galluccio, A., Goddyn, L., Hell, P.: High girth graphs avoiding a minor are nearly bipartite. J. Combin. Theory Ser. B, 83, 1–14 (2001)
Grötzsch, H.: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel. Math. Natur. Reihe, 8, 109–120 (1959)
Han, M., Li, J., Wu, Y., et al.: Counterexamples to Jaeger’s Circular Flow Conjecture. J. Combin. Theory Ser. B, 131, 1–11 (2018)
Hilton, A., Rado, R., Scott, S.: A (< 5)-color theorem for planar graphs. Bull. Lond. Math. Soc., 5, 302–306 (1973)
Hu, X., Li, J.: Circular coloring and fractional coloring in planar graphs. J. Graph Theory, 2021 https://doi.org/10.1002/jgt.22742
Jaeger, F.: Nowhere-zero flow problems, In: Selected Topics in Graph Theory 3, (L. W. Beineke and R. J. Wilson eds.), Academic Press, London, 71–95 (1988)
Klostermeyer, W., Zhang, C.-Q.: (2 + ϵ)-coloring of planar graphs with large odd girth, J. Graph Theory, 33, 109–119 (2000)
Lovász, L. M., Thomassen, C., Wu, Y., et al.: Nowhere-zero 3-flows and modulo k-orientations. J. Combin. Theory Ser. B, 103, 587–598 (2013)
Naserasr, R.: Mapping planar graphs into projective cubes. J. Graph Theory, 74(3), 249–259 (2013)
Nesetril, J., Zhu, X.: On bounded tree-width duality of graphs. J. Graph Theory, 23, 151–162 (1996)
Postle, L., Smith-Roberge, E.: On the density of C7-critical graphs. Acta Math. Univ. Comenian. (N.S.), 88(3), 1009–1016 (2019)
Thomassen, C.: The weak 3-flow conjecture and the weak circular flow conjecture. J. Combin. Theory Ser. B, 102, 521–529 (2012)
Tutte, W. T.: A contribution on the theory of chromatic polynomial. Canad. J. Math., 6, 80–91 (1954)
Zhu, X.: Circular chromatic number of planar graphs of large odd girth. Electron. J. Combin., 8, R25, 11 pp. (2001)
Acknowledgements
We sincerely thank all the referees for their time and helpful comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
The first author was partially supported by the National Natural Science Foundation of China (Grant No. 11971196) and Hubei Provincial Science and Technology Innovation Base (Platform) Special Project 2020DFH002; the second author was partially supported by the National Natural Science Foundation of China (Grant Nos. 11901318, 12131013) and the Young Elite Scientists Sponsorship Program by Tianjin (Grant No. TJSQNTJ-2020-09)
Rights and permissions
About this article
Cite this article
Hu, X.L., Li, J.A. Fractional Coloring Planar Graphs under Steinberg-type Conditions. Acta. Math. Sin.-English Ser. 39, 904–922 (2023). https://doi.org/10.1007/s10114-022-1085-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10114-022-1085-7