{"id":"arxiv/2606.27131","url":"https://arxiv.org/abs/2606.27131","tags":["math.CO"],"score":0,"title":"Exploring the world of edge-chromatic 3-critical graphs","domain":"math.CO","source":"arxiv","authors":["Le Chen","Songling Shan"],"reviews":0,"subject":"math.CO","summary":"A graph $G$ with maximum degree $Δ$ is $Δ$-critical if it is connected, satisfies $χ'(G)=Δ+1$, and the deletion of any edge reduces its chromatic index to $Δ$. A $Δ$-critical graph $G$ is called nontrivial if it contains no $Δ$-overfull subgraph; that is, no $H \\subseteq G$ such that $|E(H)| > Δ\\lfloor |V(H)| /2 \\rfloor$. There are no $1$-critical graphs, and the $2$-critical graphs are exactly the odd cycles. By work of Chetwynd and Yap from 1983, there is a unique nontrivial $3$-critical graph of order $9$, and exactly two nontrivial $3$-critical graphs of order $11$. In 2005, Bokal,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-25","reactions":{}}