Geodesic
Double-critical graphs and complete minors
The electronic journal of combinatorics, Tome 17 (2010)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv EuDML
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 
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
@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

Cité par Sources :