Geodesic
Double-critical graphs and complete minors
The electronic journal of combinatorics, Tome 17 (2010)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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$ at most $5$. We prove for $k=6$ and $k=7$ that any non-complete double-critical $k$-chromatic graph is $6$-connected and contains a complete $k$-graph as a minor.
DOI : 10.37236/359
Classification : 05C15, 05C83 
@article{10_37236_359,
     author = {Ken-ichi Kawarabayashi and Anders Sune Pedersen and Bjarne Toft},
     title = {Double-critical graphs and complete minors},
     journal = {The electronic journal of combinatorics},
     year = {2010},
     volume = {17},
     doi = {10.37236/359},
     zbl = {1215.05069},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/359/}
}
TY  - JOUR
AU  - Ken-ichi Kawarabayashi
AU  - Anders Sune Pedersen
AU  - Bjarne Toft
TI  - Double-critical graphs and complete minors
JO  - The electronic journal of combinatorics
PY  - 2010
VL  - 17
UR  - http://geodesic.mathdoc.fr/articles/10.37236/359/
DO  - 10.37236/359
ID  - 10_37236_359
ER  - 
%0 Journal Article
%A Ken-ichi Kawarabayashi
%A Anders Sune Pedersen
%A Bjarne Toft
%T Double-critical graphs and complete minors
%J The electronic journal of combinatorics
%D 2010
%V 17
%U http://geodesic.mathdoc.fr/articles/10.37236/359/
%R 10.37236/359
%F 10_37236_359
Ken-ichi Kawarabayashi; Anders Sune Pedersen; Bjarne Toft. Double-critical graphs and complete minors. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/359

Cité par Sources :