Mathematics – Combinatorics
Scientific paper
2011-07-11
Mathematics
Combinatorics
14 pages
Scientific paper
For a graph $G$, let $\chi(G)$ denote its chromatic number and $\sigma(G)$ denote the order of the largest clique subdivision in $G$. Let H(n) be the maximum of $\chi(G)/\sigma(G)$ over all $n$-vertex graphs $G$. A famous conjecture of Haj\'os from 1961 states that $\sigma(G) \geq \chi(G)$ for every graph $G$. That is, $H(n) \leq 1$ for all positive integers $n$. This conjecture was disproved by Catlin in 1979. Erd\H{o}s and Fajtlowicz further showed by considering a random graph that $H(n) \geq cn^{1/2}/\log n$ for some absolute constant $c>0$. In 1981 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 we prove the Erd\H{o}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 $n$ vertices with independence number $\alpha$.
Fox Jacob
Lee Choongbum
Sudakov Benny
No associations
LandOfFree
Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-137158