Double-critical graphs and complete minors
| dc.creator | Kawarabayashi, Ken-ichi | |
| dc.creator | Pedersen, Anders Sune | |
| dc.creator | Toft, Bjarne | |
| dc.date | 2008-10-17 | |
| dc.date.accessioned | 2026-07-07T10:10:59Z | |
| dc.date.available | 2026-07-07T10:10:59Z | |
| dc.description | A connected $k$-chromatic graph $G$ is double-critical if for all edges $uv$ of $G$ the graph $G - u - v$ is $(k-2)$-colourable. The only known double-critical $k$-chromatic graph is the complete $k$-graph $K_k$. The conjecture that there are no other double-critical graphs is a special case of a conjecture from 1966, due to Erdős and Lovász. The conjecture has been verified for $k \leq 5$. We prove for $k=6$ and $k=7$ that any non-complete double-critical $k$-chromatic graph is 6-connected and has $K_k$ as a minor. | |
| dc.identifier | https://arxiv.org/abs/0810.3133 | |
| dc.identifier | http://arxiv.org/abs/0810.3133 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/171751 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C15 | |
| dc.title | Double-critical graphs and complete minors | |
| dc.type | text |