Cubic graphs of colouring defect 3 and conjectures of Berge and Alon-Tarsi
Ján Karabáš, Edita Máčajová, Roman Nedela, Martin Škoviera · 2025
Read Cubic graphs of colouring defect 3 and conjectures of Berge and Alon-Tarsi by Ján Karabáš, Edita Máčajová, Roman Nedela, Martin Škoviera (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-17569.txt.
Description
Four mathematicians wrote a paper in two thousand twenty-five on coloring the edges of cubic graphs, graphs where each point has three links. Some such graphs cannot be colored cleanly with three sets of paired edges, called perfect matchings. The authors study how far a graph falls short, using a measure they call colouring defect.
They give a full account of the graphs whose defect is three and whose edges need at least five matchings to cover. Every such graph, they show, grows out of the famous Petersen graph by swapping in pieces that do color cleanly. They then use that account to test two long-standing conjectures in the field.
Catalog record
| CREATOR | Ján Karabáš, Edita Máčajová, Roman Nedela, Martin Škoviera |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 89 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-17569