×

Proof of the Erdős-Faudree conjecture on quadrilaterals. (English) Zbl 1223.05145

Summary: In this paper, we prove the Erdős-Faudree’s conjecture: If \(G\) is a graph of order \(4k\) and the minimum degree of \(G\) is at least \(2k\) then \(G\) contains \(k\) disjoint cycles of length 4.

MSC:

05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bollobás B.: Extremal Graph Theory. Academic Press, London (1978)
[2] Corrádi K., Hajnal A.: On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar. 14, 423–439 (1963) · Zbl 0118.19001 · doi:10.1007/BF01895727
[3] El-Zahar M.H.: On circuits in graphs. Discrete Math. 50, 227–230 (1984) · Zbl 0539.05040 · doi:10.1016/0012-365X(84)90050-5
[4] Erdos, P.: Some recent combinatorial problems, Technical Report, University of Bielefeld (1990)
[5] Komlós J., Sárközy G.N., Szemerédi E.: Proof of the Alon-Yuster conjecture. Discrete Math. 235, 255–269 (2001) · Zbl 0977.05106 · doi:10.1016/S0012-365X(00)00279-X
[6] Randerath B., Schiermeyer I., Wang H.: On quadrilaterals in a graph. Discrete Math. 203, 229–237 (1999) · Zbl 0932.05046 · doi:10.1016/S0012-365X(99)00053-9
[7] Wang H.: On quadrilaterals in a graph. Discrete Math. 288, 149–166 (2004) · Zbl 1102.05051 · doi:10.1016/j.disc.2004.02.020
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.