𝔖 Bobbio Scriptorium
✦   LIBER   ✦

M-degrees of quadrangle-free planar graphs

✍ Scribed by Oleg V. Borodin; Alexandr V. Kostochka; Naeem N. Sheikh; Gexin Yu

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
101 KB
Volume
60
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The M‐degree of an edge xy in a graph is the maximum of the degrees of x and y. The M‐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, He et al showed that every planar graph G without leaves and 4‐cycles has M‐degree at most 8 and gave an example of such a graph with M‐degree 3. This yields upper bounds on the game chromatic number of C~4~‐free planar graphs. We determine the maximum possible M‐degrees for planar, projective‐planar and toroidal graphs without leaves and 4‐cycles. In particular, for planar and projective‐planar graphs this maximum is 7. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 80–85, 2009

📜 SIMILAR VOLUMES

Total colorings of planar graphs with la
Total colorings of planar graphs with large maximum degree
✍ Borodin, O. V.; Kostochka, A. V.; Woodall, D. R. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 3 views

It is proved that a planar graph with maximum degree ∆ ≥ 11 has total (vertex-edge) chromatic number ∆ + 1.

Light subgraphs in planar graphs of mini
Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9
✍ B. Mohar; R. Škrekovski; H.-J. Voss 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 326 KB 👁 1 views

## Abstract A graph __H__ is light in a given class of graphs if there is a constant __w__ such that every graph of the class which has a subgraph isomorphic to __H__ also has a subgraph isomorphic to __H__ whose sum of degrees in __G__ is ≤ __w__. Let $\cal G$ be the class of simple planar graphs

On total 9-coloring planar graphs of max
On total 9-coloring planar graphs of maximum degree seven
✍ Sanders, Daniel P.; Zhao, Yue 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 3 views

Given a graph G, a total k-coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If ∆(G) is the maximum degree of G, then no graph has a total ∆-coloring, but Vizing conjectured that every graph has a total (∆ + 2)-coloring. This Total Coloring Conjecture rem

Total chromatic number of planar graphs
Total chromatic number of planar graphs with maximum degree ten
✍ Weifan Wang 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB 👁 1 views

## Abstract In this article we prove that the total chromatic number of a planar graph with maximum degree 10 is 11. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 91–102, 2007

Acyclic edge coloring of triangle-free p
Acyclic edge coloring of triangle-free planar graphs
✍ Manu Basavaraju; L. Sunil Chandran 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 233 KB 👁 1 views

An __acyclic__ edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The __acyclic chromatic index__ of a graph is the minimum number __k__ such that there is an acyclic edge coloring using __k__ colors and is denoted by __a__′(__G__). It was conjectured by Al