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
    0 references
    0 references
    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
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references