✦ LIBER ✦

Structural theorem on plane graphs with application to the entire coloring number

✍ Scribed by Borodin, Oleg V.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 477 KB
Volume: 23
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199611)23:3<233::aid-jgt3>3.0.co;2-t

No coin nor oath required. For personal study only.

✦ Synopsis

In 1973, Kronk and Mitchem (Discrete Math. (5) 255-260) conjectured that the vertices, edges and faces of each plane graph G may be colored with D(G) + 4 colors, where D(G) is the maximum degree of G, so that any two adjacent or incident elements receive distinct colors. They succeeded in verifying this for D(G) = 3. A structural theorem on plane graphs is proved in the present paper which implies the validity of this conjecture for all D(G) 2 7.

📜 SIMILAR VOLUMES

On Structure of Some Plane Graphs with A

On Structure of Some Plane Graphs with Application to Choosability

✍ Peter Che Bor Lam; Wai Chee Shiu; Baogang Xu 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 180 KB

A graph G=(V, E) is (x, y)-choosable for integers x> y 1 if for any given family In this paper, structures of some plane graphs, including plane graphs with minimum degree 4, are studied. Using these results, we may show that if G is free of k-cycles for some k # [3,4,5,6], or if any two triangles