Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz

preprint2012arXivOpen access

Abstract

For a graph GG, let χ(G)χ(G) denote its chromatic number and σ(G)σ(G) denote the order of the largest clique subdivision in GG. Let H(n) be the maximum of χ(G)/σ(G)χ(G)/σ(G) over all nn-vertex graphs GG. A famous conjecture of Hajós from 1961 states that σ(G)≥χ(G)σ(G) \geq χ(G) for every graph GG. That is, H(n)≤1H(n) \leq 1 for all positive integers nn. This conjecture was disproved by Catlin in 1979. Erdős and Fajtlowicz further showed by considering a random graph that H(n)≥cn1/2/log⁡nH(n) \geq cn^{1/2}/\log n for some absolute constant c>0c>0. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant CC such that χ(G)/σ(G)≤Cn1/2/log⁡nχ(G)/σ(G) \leq Cn^{1/2}/\log n for all nn-vertex graphs GG. In this paper we prove the Erdős-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can find in every graph on nn vertices with independence number αα.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.