×

High-girth graphs avoiding a minor are nearly bipartite. (English) Zbl 1028.05034

Summary: Let \(H\) be a fixed graph. We show that any \(H\)-minor free graph \(G\) of high enough girth has circular chromatic number arbitrarily close to two. Equivalently, each such graph \(G\) admits a homomorphism to a large odd circuit. In particular, graphs of high girth and of bounded genus, or of bounded tree width, are “nearly bipartite” in this sense. For example, any planar graph of girth at least 16 admits a homomorphism to a pentagon. We also obtain tight bounds on the girth of \(G\) in a few specific cases of small forbidden minors \(H\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C83 Graph minors
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Albertson, and, E. Moore, personal communication.; M. Albertson, and, E. Moore, personal communication.
[2] Bollobás, B., Extremal graph theory, Handbook of Combinatorics (1995), Elsevier: Elsevier Amsterdam · Zbl 0844.05054
[3] Bollobás, B.; Thomason, A., Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs, Europ. J. Combin., 19, 883-887 (1998) · Zbl 0918.05095
[4] Cook, R. J., Analogues of Heawood’s theorem, Combinatorics, Proc. British Combinatorial Conference. Combinatorics, Proc. British Combinatorial Conference, London Math. Society Lecture Note Series, 13 (1974), Cambridge Univ. Press: Cambridge Univ. Press London, p. 27-33 · Zbl 0319.05104
[5] Cook, R. J., Chromatic number and girth, Period. Math. Hungar., 6, 103-107 (1975) · Zbl 0313.05107
[6] M. De Vos, L. Goddyn, and, B. Mohar, Circular chromatic numbers of highly representative graphs on a surface, in preparation.; M. De Vos, L. Goddyn, and, B. Mohar, Circular chromatic numbers of highly representative graphs on a surface, in preparation.
[7] Gerards, A. M.H., Homomorphisms of graphs into odd cycles, J. Graph Theory, 12, 73-83 (1988) · Zbl 0691.05013
[8] Goddyn, L. A.; Tarsi, M.; Zhang, C.-Q., On \((k, d)\)-colorings and fractional nowhere zero flows, J. Graph Theory, 28, 155-161 (1998) · Zbl 0922.05027
[9] Grötzsch, H., Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Math. Nat. Reihe, 8, 109-120 (1959)
[10] Hell, P.; Zhu, X., The circular chromatic number of series-parallel graphs, J. Graph Theory, 33, 14-24 (2000) · Zbl 0944.05037
[11] Jaeger, F., Nowhere-zero flow problems, Selected Topics in Graph Theory (1988), Academic Press: Academic Press New York, p. 71-96
[12] A. V. Kostochka, Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica41984, 307-316, 1984.; A. V. Kostochka, Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica41984, 307-316, 1984. · Zbl 0555.05030
[13] Kronk, H. V.; White, A. T., A 4-color theorem for toroidal graphs, Proc. Amer. Math. Soc., 34, 83-86 (1972) · Zbl 0219.05057
[14] Mader, W., Homomorphieeigenschaften und mittlere Kantendichte von Graphen, Math. Ann., 174, 265-268 (1967) · Zbl 0171.22405
[15] Nešetřil, J.; Zhu, X., On bounded treewidth duality of graphs, J. Graph Theory, 23, 151-162 (1996) · Zbl 0858.05045
[16] Robertson, N.; Seymour, P. D., Graph minors. II. Algorithmic aspects of treewidth, J. Algorithms, 7, 309-322 (1986) · Zbl 0611.05017
[17] Seymour, P. D., Matroid theory, (Graham, R.; Grötschel, M.; Lovász, L., Handbook of Combinatorics (1995), Elsevier: Elsevier Amsterdam) · Zbl 0853.05024
[18] Seymour, P. D., Nowhere-zero flows, (Graham, R.; Grötschel, M.; Lovász, L., Handbook of Combinatorics (1995), Elsevier: Elsevier Amsterdam) · Zbl 0474.05028
[19] Thomason, A., An extremal function for contracting of graphs, Math. Proc. Cambridge Philos. Soc., 95, 261-265 (1984) · Zbl 0551.05047
[20] Thomassen, C., Paths, circuits and subdivisions, Selected Topics in Graph Theory (1988), Academic Press: Academic Press New York, p. 97-131 · Zbl 0659.05062
[21] Thomassen, C., Grötzsch’s theorem and its counterparts for the torus and the projective plane, J. Combin. Theory Ser. B, 62, 268-279 (1994) · Zbl 0817.05024
[22] Thomassen, C., Embeddings and minors, (Graham, R.; Grötschel, M.; Lovász, L., Handbook of Combinatorics (1995), Elsevier: Elsevier Amsterdam) · Zbl 0851.05043
[23] Youngs, D. A., 4-chromatic projective graphs, J. Graph Theory, 21, 219-227 (1996) · Zbl 0839.05040
[24] C. Q. Zhang, Circular flows of nearly eulerian graphs and vertex-splitting, preprint, 1999.; C. Q. Zhang, Circular flows of nearly eulerian graphs and vertex-splitting, preprint, 1999.
[25] Zhu, X., Circular chromatic numbers: A survey, Discrete Math., 229, 371-410 (2001) · Zbl 0973.05030
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.