𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Edge-face coloring of plane graphs with maximum degree nine

✍ Scribed by Jean-Sébastien Sereni; Matěj Stehlík

Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
189 KB
Volume
66
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

An edge-face coloring of a plane graph with edge set E and face set F is a coloring of the elements of E ∪F so that adjacent or incident elements receive different colors. Borodin [Discrete Math 128(1-3): [21][22][23][24][25][26][27][28][29][30][31][32][33] 1994] proved that every plane graph of maximum degree ≥ 10 can be edge-face colored with +1 colors. We extend Borodin's result to the case where = 9.

📜 SIMILAR VOLUMES

Acyclic edge coloring of graphs with max
Acyclic edge coloring of graphs with maximum degree 4
✍ Manu Basavaraju; L. Sunil Chandran 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 1 views

## Abstract 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 conj

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.

The size of edge chromatic critical grap
The size of edge chromatic critical graphs with maximum degree 6
✍ Rong Luo; Lianying Miao; Yue Zhao 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 216 KB 👁 1 views

## Abstract In 1968, Vizing [Uaspekhi Mat Nauk 23 (1968) 117–134; Russian Math Surveys 23 (1968), 125–142] conjectured that for any edge chromatic critical graph ${{G}} = ({{V}}, {{E}})$ with maximum degree $\Delta$, $|{{E}}| \geq {{{1}}\over {{2}}}\{(\Delta {{- 1}})|{{V}}| + {{3}}\}$. This conject