×

On the density of \(C_7\)-critical graphs. (English) Zbl 1513.05270

H. Grötzsch [Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe 6, 697–704, 785–788, 789–798 (1957; Zbl 0089.39506)] proved that every planar graph of girth at least 4 is 3-colorable (or, equivalently, admits a homomorphism to \(C_{3}\)). A generalization of this is the following conjecture: for every positive integer \(t\), every planar graph of girth at least \(4t\) admits a homomorphism to \(C_{2t+1}\). L. M. Lovász et al. [J. Comb. Theory, Ser. B 103, No. 5, 587–598 (2013; Zbl 1301.05154)] showed that every \(6t\)-edge connected graph admits a modulo \((2t+1)\)-orientation. This implies that every planar graph of girth at least \(6t\) admits a homomorphism to \(C_{2t+1}\). The authors improve upon this when \(t=3\) by showing that every planar graph of girth at least 16 admits a homomorphism to \(C_{7}\). Using the density of a graph, they first show that for any \(C_{7}\)-critical graph \(G \neq C_{3}, C_{5}\), \(e(G) \geq (17v(G)-2)/15\) which implies that any planar or projective planar graph of girth at least 17 admits a homomorphism to \(C_{7}\). Applying a lemma of W. Klostermeyer and C. Q. Zhang [J. Graph Theory 33, No. 2, 109–119 (2000; Zbl 0944.05046)] the girth bound can be lowered to 16.

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory

References:

[1] Borodin, O.; Kim, S-J; Kostochka, A.; West, D., Homomorphisms from sparse graphs with large girth, Journal of Combinatorial Theory, Series B, 90, 147-159 (2004) · Zbl 1033.05037 · doi:10.1016/S0095-8956(03)00081-9
[2] Cranston, D. W.; Li, J., Circular Flows in Planar Graphs, SIAM Journal on Discrete Mathematics, 34, 497-519 (2020) · Zbl 1433.05137 · doi:10.1137/19M1242513
[3] Dirac, G. A., Note on the colouring of graphs, Mathematische Zeitschrift, 54, 347-353 (1951) · Zbl 0043.38502 · doi:10.1007/BF01238034
[4] Dvořák, Z.; Postle, L., Density of 5/2-critical graphs, Combinatorica, 37, 863-886 (2017) · Zbl 1399.05072 · doi:10.1007/s00493-016-3356-3
[5] Grötzsch, H., Ein dreifarbensatz fur dreikreisfreie netze auf der kugel, Wiss. Z. Martin Luther Univ. Halle-Wittenberg, Math. Nat. Reihe, 8, 109-120 (1959)
[6] Han, M.; Li, J.; Wu, Y.; Zhang, C., Counterexamples to Jaeger’s circular flow conjecture, Journal of Combinatorial Theory, Series B, 131, 1-11 (2018) · Zbl 1387.05107 · doi:10.1016/j.jctb.2018.01.002
[7] F. Jaeger: On circular flows in graphs, in: Finite and infinite sets, 391-402. Elsevier, 1984. · Zbl 0567.05049
[8] Klostermeyer, W.; Zhang, C., (2 + ∊)-coloring of planar graphs with large odd-girth, Journal of Graph Theory, 33, 109-119 (2000) · Zbl 0944.05046 · doi:10.1002/(SICI)1097-0118(200002)33:2<109::AID-JGT5>3.0.CO;2-F
[9] Kostochka, A.; Yancey, M., Ore’s conjecture on color-critical graphs is almost true, Journal of Combinatorial Theory, Series B, 109, 73-101 (2014) · Zbl 1301.05127 · doi:10.1016/j.jctb.2014.05.002
[10] Lovász, L.; Thomassen, C.; Wu, Y.; Zhang, C., Nowhere-zero 3-flows and modulo k-orientations, Journal of Combinatorial Theory, Series B, 103, 587-598 (2013) · Zbl 1301.05154 · doi:10.1016/j.jctb.2013.06.003
[11] Nešetřil, J.; Zhu, X., On bounded tree-width duality of graphs, J. Graph Theory, 23, 151-162 (1996) · Zbl 0858.05045 · doi:10.1002/(SICI)1097-0118(199610)23:2<151::AID-JGT6>3.0.CO;2-S
[12] Ore, O., The Four-Color Problem (1967), New York: Academic Press, New York · Zbl 0149.21101
[13] Zhu, X., Circular chromatic number: a survey, Discrete Mathematics, 229, 371-410 (2001) · Zbl 0973.05030 · doi:10.1016/S0012-365X(00)00217-X
[14] Zhu, X., Circular chromatic number of planar graphs of large odd girth, The Electronic Journal of Combinatorics, 8, 25 (2001) · Zbl 0969.05022 · doi:10.37236/1569
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.