Geodesic
Face-degree bounds for planar critical graphs
Ligang Jin1 ; Yingli Kang1 ; Eckhard Steffen2
1Paderborn University Institute of Mathematics Warburger Str. 100 33098 Paderborn
2Paderborn University Institute of Mathematics and Paderborn Center for Advanced Studies Warburger Str. 100 33098 Paderborn
The electronic journal of combinatorics, Tome 23 (2016) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The only remaining case of a well known conjecture of Vizing states that there is no planar graph with maximum degree 6 and edge chromatic number 7. We introduce parameters for planar graphs, based on the degrees of the faces, and study the question whether there are upper bounds for these parameters for planar edge-chromatic critical graphs. Our results provide upper bounds on these parameters for smallest counterexamples to Vizing's conjecture, thus providing a partial characterization of such graphs, if they exist.For $k \leq 5$ the results give insights into the structure of planar edge-chromatic critical graphs.
DOI : 10.37236/5895
Classification : 05C10, 05C15
Mots-clés : Vizing's planar graph conjecture, planar graph, critical graphs, edge coloring

Ligang Jin  1   ; Yingli Kang  1   ; Eckhard Steffen  2

1 Paderborn University Institute of Mathematics Warburger Str. 100 33098 Paderborn
2 Paderborn University Institute of Mathematics and Paderborn Center for Advanced Studies Warburger Str. 100 33098 Paderborn 
@article{10_37236_5895,
     author = {Ligang Jin and Yingli Kang and Eckhard Steffen},
     title = {Face-degree bounds for planar critical graphs},
     journal = {The electronic journal of combinatorics},
     year = {2016},
     volume = {23},
     number = {3},
     doi = {10.37236/5895},
     zbl = {1344.05052},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/5895/}
}
TY  - JOUR
AU  - Ligang Jin
AU  - Yingli Kang
AU  - Eckhard Steffen
TI  - Face-degree bounds for planar critical graphs
JO  - The electronic journal of combinatorics
PY  - 2016
VL  - 23
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/5895/
DO  - 10.37236/5895
ID  - 10_37236_5895
ER  - 
%0 Journal Article
%A Ligang Jin
%A Yingli Kang
%A Eckhard Steffen
%T Face-degree bounds for planar critical graphs
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/5895/
%R 10.37236/5895
%F 10_37236_5895
Ligang Jin; Yingli Kang; Eckhard Steffen. Face-degree bounds for planar critical graphs. The electronic journal of combinatorics, Tome 23 (2016) no. 3. doi: 10.37236/5895

Cité par Sources :