Decomposing a planar graph of girth 5 into an independent set and a forest

Publication: Research - peer-reviewJournal article – Annual report year: 2009

View graph of relations

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 languageEnglish
JournalJournal of Combinatorial Theory. Series B
Publication date2009
Volume99
Issue4
Pages674-684
ISSN0095-8956
DOIs
StatePublished
CitationsWeb of Science® Times Cited: 3

Keywords

  • Forests, Independent sets, Planar graphs of girth 5
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 3420045