Erdős Problem #108
For every r ≥ 4 and k ≥ 2 is there some finite f(k,r) such that every graph of chromatic number ≥ f(k,r) contains a subgraph of girth ≥ r and chromatic number ≥ k?
No claims yet Be the first →
Open problems about cycles in graphs
Which cycle lengths must a graph contain given its edge count, minimum degree or chromatic number? Small counterexamples, if any exist, can be searched for exhaustively.
Erdős Problem #184
Any graph on n vertices can be decomposed into O(n) many edge-disjoint cycles and edges.
No claims yet Be the first →
Erdős Problem #572
Show that for k≥ 3 ex(n;C_2k)≫ n^1+1/k. This problem is #46 in Extremal Graph Theory in the graphs problem collection.
No claims yet Be the first →
Erdős Problem #60
Does every graph on n vertices with >ex(n;C_4) edges contain ≫ n^1/2 many copies of C_4?
No claims yet Be the first →
Erdős Problem #64
Does every finite graph with minimum degree at least 3 contain a cycle of length 2^k for some k ≥ 2?
No claims yet Be the first →
Erdős Problem #65
Is the sum Σ1/a_i minimised when G is a complete bipartite graph? This problem is #65 in Extremal Graph Theory in the graphs problem collection.
No claims yet Be the first →