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 statement3 of 7

Dirac's conjecture was proved, for $k=5$ : There exists a graph $G$ with chromatic number $5$ , such that every vertex is critical, yet every critical set of edges has size $>1$ , or in other words: has no critical edge.

[Br92] Brown, Jason I., A vertex critical graph without critical edges. Discrete Math. (1992), 99--101

FormalConjectures/ErdosProblems/944.leanErdos944.erdos_944.variants.dirac_conjecture.k_eq_51 lineExact file

1∃ V G, Erdos944.SimpleGraph.IsErdos944 G 5 1

SolvedStatement only, no proof

Sources

Search problems.science