Abstract
We use a list-color technique to extend the result of Borodin and Glebov that the vertex set of every planar graph of girth at least 5 can be partitioned into an independent set and a set which induces a forest. We apply this extension to also extend Grötzsch's theorem that every planar triangle-free graph is 3-colorable. Let G be a plane graph. Assume that the distance between any two triangles is at least 4. Assume also that each triangle contains a vertex such that this vertex is on the outer face boundary and is not contained in any 4-cycle. Then G has chromatic number at most 3. Note that, in this extension of Grötzsch's theorem an unbounded number of triangles are allowed.
| Original language | English |
|---|---|
| Journal | Journal of Combinatorial Theory. Series B |
| Volume | 99 |
| Issue number | 4 |
| Pages (from-to) | 674-684 |
| ISSN | 0095-8956 |
| DOIs | |
| Publication status | Published - 2009 |
Keywords
- Forests
- Independent sets
- Planar graphs of girth 5
Fingerprint
Dive into the research topics of 'Decomposing a planar graph of girth 5 into an independent set and a forest'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver