Berge's conjecture for cubic graphs with small colouring defect
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909451797135360 |
|---|---|
| author | Karabáš, Ján Máčajová, Edita Nedela, Roman Škoviera, Martin |
| author_facet | Karabáš, Ján Máčajová, Edita Nedela, Roman Škoviera, Martin |
| contents | A long-standing conjecture of Berge suggests that every bridgeless cubic graph can be expressed as a union of at most five perfect matchings. This conjecture trivially holds for $3$-edge-colourable cubic graphs, but remains widely open for graphs that are not $3$-edge-colourable. The aim of this paper is to verify the validity of Berge's conjecture for cubic graphs that are in a certain sense close to $3$-edge-colourable graphs. We measure the closeness by looking at the colouring defect, which is defined as the minimum number of edges left uncovered by any collection of three perfect matchings. While $3$-edge-colourable graphs have defect $0$, every bridgeless cubic graph with no $3$-edge-colouring has defect at least $3$. In 2015, Steffen proved that the Berge conjecture holds for cyclically $4$-edge-connected cubic graphs with colouring defect $3$ or $4$. Our aim is to improve Steffen's result in two ways. We show that all bridgeless cubic graphs with defect $3$ satisfy Berge's conjecture irrespectively of their cyclic connectivity. If, additionally, the graph in question is cyclically $4$-edge-connected, then four perfect matchings suffice, unless the graph is the Petersen graph. The result is best possible as there exists an infinite family of cubic graphs with cyclic connectivity $3$ which have defect $3$ but cannot be covered with four perfect matchings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_13234 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Berge's conjecture for cubic graphs with small colouring defect Karabáš, Ján Máčajová, Edita Nedela, Roman Škoviera, Martin Combinatorics 05C15, 05C70, 05C75 A long-standing conjecture of Berge suggests that every bridgeless cubic graph can be expressed as a union of at most five perfect matchings. This conjecture trivially holds for $3$-edge-colourable cubic graphs, but remains widely open for graphs that are not $3$-edge-colourable. The aim of this paper is to verify the validity of Berge's conjecture for cubic graphs that are in a certain sense close to $3$-edge-colourable graphs. We measure the closeness by looking at the colouring defect, which is defined as the minimum number of edges left uncovered by any collection of three perfect matchings. While $3$-edge-colourable graphs have defect $0$, every bridgeless cubic graph with no $3$-edge-colouring has defect at least $3$. In 2015, Steffen proved that the Berge conjecture holds for cyclically $4$-edge-connected cubic graphs with colouring defect $3$ or $4$. Our aim is to improve Steffen's result in two ways. We show that all bridgeless cubic graphs with defect $3$ satisfy Berge's conjecture irrespectively of their cyclic connectivity. If, additionally, the graph in question is cyclically $4$-edge-connected, then four perfect matchings suffice, unless the graph is the Petersen graph. The result is best possible as there exists an infinite family of cubic graphs with cyclic connectivity $3$ which have defect $3$ but cannot be covered with four perfect matchings. |
| title | Berge's conjecture for cubic graphs with small colouring defect |
| topic | Combinatorics 05C15, 05C70, 05C75 |
| url | https://arxiv.org/abs/2210.13234 |