Any graph of large chromatic number has many edge-disjoint cycles on one subset of vertices
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 \(k\) edge-disjoint cycles on the same set of vertices?Bibliography | |
---|---|
1 | P. Erdös, Some recent problems and results in graph theory, Discrete Math. 164 (1997) no. 1, 93–96. |