Geodesic
Minimax degrees of quasiplane graphs without $4$-faces
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 4 (2007), pp. 435-439

Voir la notice de l'article provenant de la source Math-Net.Ru

The $M$-degree of an edge $xy$ in a graph is the maximum of the degrees of $x$ and $y$. The minimax degree of a graph $G$ is the minimum over $M$-degrees of its edges. In order to get upper bounds on the game chromatic number, W. He et al showed that every planar graph $G$ without leaves and $4$-cycles has minimax degree at most $8$. This was improved by Borodin et al to the best possible bound $7$. Answering a question by D. West, we show that every plane graph $G$ without leaves and $4$-faces has minimax degree at most $15$. The bound is sharp. Similar results are obtained for graphs embeddable on the projective plane, torus and Klein bottle. 
@article{SEMR_2007_4_a24,
     author = {O. V. Borodin and A. O. Ivanova and A. V. Kostochka and N. N. Sheikh},
     title = {Minimax degrees of quasiplane graphs without $4$-faces},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {435--439},
     publisher = {mathdoc},
     volume = {4},
     year = {2007},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2007_4_a24/}
}
TY  - JOUR
AU  - O. V. Borodin
AU  - A. O. Ivanova
AU  - A. V. Kostochka
AU  - N. N. Sheikh
TI  - Minimax degrees of quasiplane graphs without $4$-faces
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2007
SP  - 435
EP  - 439
VL  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2007_4_a24/
LA  - en
ID  - SEMR_2007_4_a24
ER  - 
%0 Journal Article
%A O. V. Borodin
%A A. O. Ivanova
%A A. V. Kostochka
%A N. N. Sheikh
%T Minimax degrees of quasiplane graphs without $4$-faces
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2007
%P 435-439
%V 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2007_4_a24/
%G en
%F SEMR_2007_4_a24
O. V. Borodin; A. O. Ivanova; A. V. Kostochka; N. N. Sheikh. Minimax degrees of quasiplane graphs without $4$-faces. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 4 (2007), pp. 435-439. http://geodesic.mathdoc.fr/item/SEMR_2007_4_a24/