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

Lattanzio [La02] proved there exist $k$ -critical graphs without critical edges for all $k$ such that $k - 1$ is not prime.

[La02] Lattanzio, John J., A note on a conjecture of {D}irac. Discrete Math. (2002), 323--330

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

1∀ (k : ℕ), 4 ≤ k → ¬Nat.Prime (k - 1) → ∃ V G, Erdos944.SimpleGraph.IsErdos944 G k 1

SolvedStatement only, no proof

Sources

Search problems.science