Another problem on almost-bipartite graphs with infinite 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
A problem on infinite chromatic numbers[1]
Let \( \kappa \geq \aleph_0\) be an arbitrary cardinal number. Is it true that there is a graph of chromatic number \( \kappa\) with the property that every subgraph on \( n\) vertices can be made bipartite by omitting \( cn\) edges?
Let \( \kappa \geq \aleph_0\) be an arbitrary cardinal number. Is it true that there is a graph of chromatic number \( \kappa\) with the property that every subgraph on \( n\) vertices can be made bipartite by omitting \( cn\) edges?
In [1], Erdös pointed out that \( o(n)\) edges will not be enough since a graph with chromatic number \( \geq \aleph_1\) must contain \( \aleph_1\) vertex-disjoint odd cycles of length \( 2r+1\) for some \( r\).
Bibliography | |
---|---|
1 | P. Erdös, Some recent problems and results in graph theory, Discrete Math. 164 (1997), 81-85. |