Erdős Problem #1068
Does every graph with chromatic number aleph_1 contain a countable subgraph which is infinitely connected?
No claims yet Be the first →
Open problems about chromatic numbers
How many colours a graph or hypergraph needs, and what forces that number up: girth, forbidden subgraphs, geometric constraints. Colourings and explicit graphs are certificates a machine can check.
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 →
Erdős Problem #1175
Let κ be an uncountable cardinal. Must there exist a cardinal λ such that every graph with chromatic number λ contains a triangle-free subgraph with chromatic number κ? Shelah proved that a negative answer is consistent when κ = λ = aleph_1 (see erdos_1175.variants.aleph_one).
No claims yet Be the first →
Erdős Problem #19
If G is an edge-disjoint union of n copies of K_n, then is χ(G) = n?
No claims yet Be the first →
Erdős Problem #593
Erdős Problem 593 (\500): Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number > aleph_0. The answer is the set of obligatory finite 3-uniform hypergraphs, represented here on the labelled vertex sets Fin n.
No claims yet Be the first →
Erdős Problem #628
Let G be a graph with chromatic number k containing no K_k. If a,b≥ 2 and a+b=k+1 then must there exist two disjoint subgraphs of G with chromatic numbers ≥ a and ≥ b respectively?
No claims yet Be the first →
Erdős Problem #740
Let m be an infinite cardinal and G be a graph with chromatic number m. Let r≥ 1. Must G contain a subgraph of chromatic number m which does not contain any odd cycle of length ≤ r?
No claims yet Be the first →
Erdős Problem #75
Is there a graph of chromatic number ℵ_ 1 with ℵ_ 1 vertices such that for all ε > 0, if n is sufficiently large and H is a subgraph on n vertices, then H contains an independent set of size > n ^ (1 - ε)?
No claims yet Be the first →
Erdős Problem #918
Erdős Problem #918
No claims yet Be the first →
Erdős Problem #944
Let k ≥ 4 and r≥ 1. Must there exist a graph G with chromatic number k such that every vertex is critical, yet every critical set of edges has size >r?
No claims yet Be the first →