Cycles of length 0 modulo 4 in graphs
type: Item
instance of: scholarly article
title: Cycles of length 0 modulo 4 in graphs
zbMATH Open document ID: 0791.05064
DOI: 10.1016/0012-365X(93)90535-2
author: Nathaniel Dean
author: Linda Lesniak
author: Akira Saito
published in: Discrete Mathematics
publication date: 1994-06-08T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 473113
zbMATH Keywords: chromatic graph
zbMATH Keywords: cycle
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: Modularity of cycles and paths in graphs
cites work: Q4873792
cites work: Q3818315
cites work: Cycles Modulo k
cites work: Large cycles in graphs
cites work: Graphs with a cycle of length divisible by three
cites work: Q4873814
cites work: Q4121920
cites work: A strengthening of the Kuratowski planarity criterion for 3-connected graphs
cites work: Q5591378
cites work: Cyclic coloration of 3-polytopes
cites work: Some Homeomorphism Properties of Graphs
cites work: Graph decomposition with applications to subdivisions and path systems modulo k
cites work: A refinement of Kuratowski's theorem
full work available at URL: 0012-365x(93)90535-2
OpenAlex ID: W2005748221
description: scientific article; zbMATH DE number 473113