Planar graphs have exponentially many 3-arboricities

DOI10.1137/110846828zbMATH Open1256.05056arXiv1110.4900OpenAlexW2059398229MaRDI QIDQ4899062FDOQ4899062

Ararat Harutyunyan, Bojan Mohar

Publication date: 4 January 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: It is well-known that every planar or projective planar graph can be 3-colored so that each color class induces a forest. This bound is sharp. In this paper, we show that there are in fact exponentially many 3-colorings of this kind for any (projective) planar graph. The same result holds in the setting of 3-list-colorings.

Full work available at URL: https://arxiv.org/abs/1110.4900

Recommendations

• Sub-exponentially many 3-colorings of triangle-free planar graphs
• Many 3-colorings of triangle-free planar graphs
• Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles
• Covering projective planar graphs with three forests
• Do triangle-free planar graphs have exponentially many 3-colorings?

zbMATH Keywords

digraph chromatic numberplanar graphvertex-arboricity

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Cited In (1)

• Do triangle-free planar graphs have exponentially many 3-colorings?

This page was built for publication: Planar graphs have exponentially many 3-arboricities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899062)