Any graph of large chromatic number has an odd cycle spanning a subgraph of large chromatic 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
In [1], Erdös and Hajnal raised the following question:
Problem
Is it true that for every \(k\), there is an \(f(k)\) so that if a graph \(G\) has chromatic number at least \(f(k)\), then it always contains an odd cycle whose vertices span a graph of chromatic number at least \(k\)?Bibliography | |
---|---|
1 | P. Erdös, Some recent problems and results in graph theory, Discrete Math. 164 (1997) no. 1, 93–96. |