Density of 5/2-critical graphs (Q1705839)

Let \(G\) be a graph. For a real number \(r\geq 1\), a function \(\phi\) from \(V (G)\) to the circle with circumference \(r\) is a circular \(r\)-coloring if for every edge \(uv\in E(G)\), the distance between \(\phi(u)\) and \(\phi(v)\) in the circle is at least one. The infimum of \(r\geq 1\) such that \(G\) has an \(r\)-coloring is called the circular chromatic number of \(G\). The circular chromatic number was introduced by \textit{A. Vince} [J. Graph Theory 12, No. 4, 551--559 (1988; Zbl 0658.05028)] who also showed that the circular chromatic number of a graph differs from the ordinary chromatic number by at most 1. It is easy to see that for an integer \(t\geq 1\), a graph \(G\) has circular chromatic number at most \(2+\frac{1}{t}\) if and only if \(G\) has a homomorphism to \(C_{2t+1}\). \textit{F. Jaeger} [in: Finite and infinite sets. (Sixth Hungarian Combinatorial Colloquium held in Eger, Hungary, July 6--11, 1981). Vols. I. Amsterdam etc.: North-Holland. 391--402 (1984; Zbl 0567.05049)] made, among others, the following conjecture: for every integer \(t\geq 1\), every planar graph of girth at least \(4t\) has a homomorphism to \(C_{2t+1}.\) The only resolved instance is \(t=1\), which is equivalent to the theorem of \textit{H. Grötzsch} [Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe 6, 697--704, 785--788, 789--798 (1957; Zbl 0089.39506)]. For general \(t\), the best known result is [\textit{O. V. Borodin} et al., ccccccccc J. Comb. Theory, Ser. B 90, No. 1, 147--159 (2004; Zbl 1033.05037)] which proves that every planar graph of girth at least \(\frac{20t-2}{3}\) has a homomorphism to \(C_{2t+1}\). For the case \(t = 2\), \textit{X. Zhu} [Electron. J. Comb. 8, No. 1, Research paper R25, 11 p. (2001; Zbl 0969.05022)] showed that every planar graph of girth at least 12 has a homomorphism to \(C_5\). The paper under review gives a strengthening of these results by showing that it is sufficient to bound only the density of the colored graph, rather than assuming its planarity. A step in this direction was [\textit{O. V. Borodin} et al., Sib. Èlektron. Mat. Izv. 5, 417--426 (2008; Zbl 1299.05115)] which proved that if \(G\) is a triangle-free graph such that \(\frac{e(H)}{n(H)} < 6/5\) for every \(H\) subgraph of \( G\), then \(G\) is 5/2-colorable. It would be possible to state the results of the paper under review similarly in the terms of the maximum edge density of subgraphs, but the authors chose to work in the setting of critical graphs, which is more convenient and slightly less restrictive. A graph \(G\) is called 5/2-critical, if \(G\) has no circular 5/2-coloring (or equivalently, homomorphism to \(C_5\)), but every proper subgraph of \(G\) has one. The main results of the paper are the following: If \(G\) is a 5/2-critical graph distinct from \(C_3\), then \(5n(G)-4e(G)\leq 2\). Every planar or projective-planar graph of girth at least 10 has a homomorphism to \(C_5\), Every planar graph without odd cycles of length at most 9 has a homomorphism to \(C_5\).