Cycles of length 0 modulo 4 in graphs (Q1309447): Difference between revisions

The authors prove the following. Every graph \(G\) with \(\delta(G) \geq 2\) and at most two vertices of degree 2 contains a cycle of length 0 mod 4. Every 4-chromatic graph contains a cycle of length 0 mod 4. If \(G\) is a graph of order \(p \geq 5\) with at least \(3p-5\) edges, then every subdivision of \(G\) contains a cycle of length 0 mod 4. To put these theorems into perspective we recall some earlier results. \textit{P. Erdős} [Proc. 7th Southeast Conf. Comb., Graph Theory, Comput., Baton Rouge 1976, 3-14 (1976; Zbl 0352.05024)] reported that Robertson showed that every graph of sufficiently large degree contains a cycle of length 0 mod \(k\). This also is a special case of a theorem of \textit{B. Bollobás} [Bull. Lond. Math. Soc. 9, 97-98 (1977; Zbl 0348.05104)]. Recently, Chen and the last author [Graphs with a cycle of length divisible by 3, J. Comb. Theory, Ser. B, to appear] proved that every graph with minimum degree 3 contains a cycle of length 0 mod 3. It follows from a result of \textit{C. Thomassen} [J. Graph Theory 7, 261-271 (1983; Zbl 0515.05052)] that minimum degree 40 gurantees the existence of a cycle of length 0 mod 4. Thus, the authors' degree theorem provides an optimal improvement over the latter result.