Skip to content

Erdős problem 944

Start work

Let k≥4k \ge 4 and r≥1r\ge 1. Must there exist a graph GG with chromatic number kk such that every vertex is critical, yet every critical set of edges has size >r>r?

Sources

The source's own material, retained exactly.

7 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

944.lean

Retained formal statement2 of 7

Let k≥4k \ge 4. Must there exist a graph GG with chromatic number kk such that every vertex is critical, yet every critical set of edges has size >1>1?

This was conjectured by Dirac in 1970.

FormalConjectures/ErdosProblems/944.leanErdos944.erdos_944.variants.dirac_conjecture1 lineExact file
True ↔ ∀ k ≥ 4, ∃ V G, Erdos944.SimpleGraph.IsErdos944 G k 1
OpenStatement only, no proof