A characterization of edge-chromatic 3-critical graphs

@misc{chen2026characterization,
  title = {{A characterization of edge-chromatic 3-critical graphs}},
  author = {Le Chen and Songling Shan},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2606.27131},
  eprint = {2606.27131},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.27131},
}

TY  - UNPB
TI  - A characterization of edge-chromatic 3-critical graphs
AU  - Le Chen
AU  - Songling Shan
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2606.27131
UR  - https://arxiv.org/abs/2606.27131
AB  - A graph with maximum degree Δ is \emph{Δ-critical} if it is connected, has chromatic index Δ+1, and the deletion of any edge reduces its chromatic index to Δ; it is \emph{nontrivial} if it has no subgraph H with |E(H)|>Δ⌊ |V(H)|/2⌋. We prove a characterization of all nontrivial $3$-critical graphs: every such graph is obtained either from smaller $3$-critical graphs by replacing a vertex with a triangle, by a Hajós-join, or by replacing a vertex with a suitable class~$1$ graph, or from a snark by deleting at most one vertex and some independent edges. The third operation, which we call a Meredith-type extension, generalizes the Meredith extension by allowing other class~$1$ graphs in place of K_2,3, and we give a sufficient condition under which it produces new nontrivial $3$-critical graphs from smaller ones. To the best of our knowledge, this is the first characterization of this kind for edge-chromatic $3$-critical graphs, and the Meredith-type extension has not previously been considered in this generality. The characterization was found by analyzing the output of an exhaustive computer search for nontrivial $3$-critical graphs of orders $13$ to $24$, and we make the resulting data publicly available. Based on these data, we also propose two conjectures that are closely related to the case Δ=3 of Seymour's exact conjecture and to Grötzsch's conjecture on the $3$-edge-colorability of planar graphs.
ER  -