Sharpening an ore-type version of the Corrádi-Hajnal theorem
type: Item
instance of: scholarly article
title: Sharpening an ore-type version of the Corrádi-Hajnal theorem
zbMATH Open document ID: 1462.05143
published in: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
publication date: 2018-01-05T00:00:00Z
review text: In this long paper, the authors studied an Ore-type version of the Corrádi-Hajnal theorem and resolved the difficult case when \(|G|=3k\). \textit{K. Corradi} and \textit{A. Hajnal} [Acta Math. Acad. Sci. Hung. 14, 423--439 (1963; Zbl 0118.19001)] proved that for all \(k \geq 1\) and \(n \geq 3 k\), every (simple) graph \(G\) on \(n\) vertices with minimum degree \(\delta(G) \geq 2 k\) contains \(k\) disjoint cycles. The degree bound is sharp. \textit{H. Enomoto} [Combinatorica 18, No. 4, 487--492 (1998; Zbl 0924.05041)] and \textit{H. Wang} [Discrete Math. 205, No. 1--3, 183--190 (1999; Zbl 0936.05063)] proved the refinement of the Corrádi-Hajnal theorem: For all \(k \geq 1\) and \(n \geq 3 k\), every graph \(G\) on \(n\) vertices contains \(k\) disjoint cycles, provided that \(d(x)+d(y) \geq 4 k-1\) for all distinct nonadjacent vertices \(x\), \(y\). Recently, it was refined for \(k \geq 3\) and \(n \geq 3 k+1\): If \(G\) is a graph on \(n\) vertices such that \(d(x)+d(y) \geq 4 k-3\) for all distinct nonadjacent vertices \(x\), \(y,\) then \(G\) has \(k\) vertex-disjoint cycles if and only if the independence number \(\alpha(G) \leq n-2 k\) and \(G\) is not one of two small exceptions in the case \(k=3\). But the difficult case, \(n=3 k,\) was not handled. In this paper, the authors resolved this difficult case using an equitable \(k\)-coloring and obtain the full picture of extremal graphs for the Ore-type version of the Corrádi-Hajnal theorem. Since any \(k\) disjoint cycles in a \(3 k\)-vertex graph \(G\) must be 3-cycles, the existence of such \(k\) cycles is equivalent to the existence of an equitable \(k\)-coloring of the complement of \(G\). This result can be also considered as an Ore-type version of a partial case of the Chen-Lih-Wu conjecture on equitable colorings.
reviewed by: Vinayak Joshi
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C07
zbMATH DE Number: 6822588
zbMATH Keywords: disjoint cycles
zbMATH Keywords: equitable coloring
zbMATH Keywords: minimum degree
author: H. A. Kierstead
author: Alexandr Kostochka
author: Theodore Molla
author: Elyse Yeager
MaRDI profile type: Publication
full work available at URL: s12188-016-0168-8
OpenAlex ID: W2565774297
cites work: Spanning subgraphs of random graphs
cites work: \(H\)-factors in dense graphs
cites work: Q2735585
cites work: Equitable coloring and the maximum degree
cites work: On the maximal number of independent circuits in a graph
cites work: On the existence of disjoint cycles in a graph
cites work: An Ore-type theorem on equitable coloring
cites work: Ore-type versions of Brooks' theorem
cites work: Every 4-colorable graph with maximum degree 4 has an equitable 4-coloring
cites work: A refinement of a result of Corrádi and Hajnal
cites work: On the Corrádi-Hajnal theorem and a question of Dirac
cites work: The \((2k-1)\)-connected multigraphs with at most \(k-1\) disjoint cycles
cites work: Graphs with chromatic number close to maximum degree
cites work: On equitable coloring of bipartite graphs
cites work: Q4255998
cites work: \(\Delta \)-critical graphs with small high vertex cliques
cites work: Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
cites work: Q4716273
cites work: On the maximum number of independent cycles in a graph
cites work: Q4348809
DOI: 10.1007/S12188-016-0168-8
Recommended article: On the Corrádi-Hajnal theorem and a question of Dirac
Recommended article: Strengthening Theorems of Dirac and Erdős on Disjoint Cycles
Recommended article: Vertex-disjoint cycles containing specified vertices in a graph
Recommended article: Disjoint chorded cycles in graphs with high Ore-degree
Recommended article: A refinement of theorems on vertex-disjoint chorded cycles
Recommended article: On the maximum number of independent cycles in a graph
Recommended article: Disjoint even cycles packing
Recommended article: Q4697568
Recommended article: Q3726164
Recommended article: Q3816097
description: scientific article; zbMATH DE number 6822588