Erdős problem 944 · problems.science

Let $k \ge 4$ and $r\ge 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$ ?

Sources

Browse retained paths and inspect the exact material available for this Problem.

7 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

944.lean

Retained formal statement7 of 7

Martinsson and Steiner [MaSt25] proved for every $r \ge 1$ if $k$ is sufficiently large, depending on $r$ , there exist a graph $G$ with chromatic number $k$ such that every vertex is critical, yet every critical set of edges has size $>r$ .

[MaSt25] Martinsson, Anders and Steiner, Raphael, Vertex-critical graphs far from edge-criticality. Combin. Probab. Comput. (2025), 151--157

FormalConjectures/ErdosProblems/944.leanErdos944.erdos_944.variants.large_k_for_any_r1 lineExact file

1∀ (r : ℕ), 1 ≤ r → ∀ᶠ (k : ℕ) in Filter.atTop, ∃ V G, Erdos944.SimpleGraph.IsErdos944 G k r

SolvedStatement only, no proof

Sources

Search problems.science