Ratio of chromatic number to clique number
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
A problem on the chromatic number and clique number (proposed by Erdös)
Let \(\omega(G)\) denote the number of vertices in a largest complete subgraph of \(G\). Let \(f(n)\) denote the maximum value of \(\chi(G)/\omega(G)\), where \(G\) ranges over all graphs on \(n\) vertices.Does the following limit exist \[ \lim_{n \rightarrow \infty} \frac{f(n)}{ n/\log^2 n}? \]
Tutte and Zykov [1] independently showed that for every \( k\), there is a graph \( G\) with \(\omega(G)=2\) (i.e., \( G\) contains no triangle), and with \( \chi(G)=k\). Erdös [2] proved that for every \( n\), there is a graph \( G\) on \( n\) vertices with \(\omega(G)=2\) and \( \chi(G) > c n^{1/2}/\log n\). Using Kim's result [3] on Ramsey numbers, it follows there is a graph \( G\) on \( n\) vertices with \( \omega(G)=2\) and with chromatic number \( \chi(G)\) satisfying
\(\displaystyle (1+o(1)) \frac 1 9 \sqrt{\frac{n}{\log n}} <\chi(G). \)
For the maximum ratio \( f(n)\) of the chromatic number and the clique number, Erdös [4] proved that
\(\displaystyle \frac{c n}{\log^2 n} \leq f(n) \leq \frac{c'n}{\log^2 n}. \)
The value of the limit
of
\( f(n)/(n/\log^2 n)\), if it exists, is shown in
[4]
to be between \( (\log n)^2/4\) and \( (\log 2)^2\).
Bibliography | |
---|---|
1 | A. A. Zykov, On some problems of linear complexes, Mat. Sbornik N. S. 24 (1949). 163-188 (in Russian). English translation in Amer. Math. Soc. Transl. 79 (1952). Reissued in Translation Series I, 7, Algebraic Topology, American Math. Soc. (1962), 418-449. |
2 | P. Erdös, Graph theory and probability, II., Canad. J. Math. 13 (1961), 346-352. |
3 | J. H. Kim, The Ramsey number \( R(3,t)\) has order of magnitude \( t^2/ \log t\), Random Structures and Algorithms 7 (1995), 173-207. |
4 | P. Erdös, Some remarks on chromatic graphs, Colloq. Math. 16 (1967), 253-256. |