✦ LIBER ✦
Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
✍ Scribed by O. V. Borodin
- Publisher
- John Wiley and Sons
- Year
- 1996
- Tongue
- English
- Weight
- 190 KB
- Volume
- 21
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
If in a plane graph with minimum degree 2 3 no t w o triangles have an edge in common, then: (1 there are two adjacent vertices with degree sum at most 9, and (2) there is a face of size between 4 and 9 or a 10-face incident with ten 3-vertices. It follows that every planar graph without cycles between 4 and 9 is 3-colorable.