About

Log in?

DTU users get better search results including licensed content and discounts on order fees.

Anyone can log in and get personalized features such as favorites, tags and feeds.

Log in as DTU user Log in as non-DTU user No thanks

DTU Findit

Journal article

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

From

National Institute of Informatics1

Discrete mathematics, Department of Mathematics, Technical University of Denmark2

Department of Mathematics, Technical University of Denmark3

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.

Language: English
Year: 2009
Pages: 674-684
ISSN: 10960902 and 00958956
Types: Journal article
DOI: 10.1016/j.jctb.2008.11.002
ORCIDs: Thomassen, Carsten

DTU users get better search results including licensed content and discounts on order fees.

Log in as DTU user

Access

Analysis