Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz (Q2448966)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz |
scientific article |
Statements
Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz (English)
0 references
5 May 2014
0 references
For a graph \(G\), let \(\chi(G)\) denote its chromatic number, \(\sigma (G)\) denote the largest integer \( p\) such that \(G\) contains a subdivision of a complete graph of order \( p\) and \(H(n)\) be the maximum of \(\chi (G)/\sigma (G)\) over all \(n\)-vertex graphs \(G\). A famous conjecture of Hajós states that \( H(n)\leq 1\) for all positive integers \(n\). This conjecture was disproved by \textit{P. A. Catlin} [J. Comb. Theory, Ser. B 26, 268--274 (1979; Zbl 0385.05033)]. \textit{P. Erdős} and \textit{S. Fajtlowicz} [Combinatorica 1, 141--143 (1981; Zbl 0504.05052)] further showed by considering a random graph that \(H(n)\geq cn^{1/2}/\log n\) for some absolute constant \(c>0\) and they conjectured that this bound is tight up to a constant factor in that there is some absolute constant \(C\) such that \(\chi (G)/\sigma (G) \leq Cn^{1/2}/\log n\) for all \(n\)-vertex graphs \(G\). In this paper the authors prove the Erdős-Fajtlowicz conjecture, deducing an estimate on the order of the largest clique subdivision which can be found in every graph on \(n\) vertices with independence number \(\alpha \).
0 references
chromatic number
0 references
clique subdivision
0 references
Erdős-Fajtlowicz conjecture
0 references
independence number
0 references
random graph
0 references
Cauchy-Schwarz inequality
0 references
vertex-disjoint paths
0 references
Turán's theorem
0 references