Graphs with bounded tree-width and large odd-girth are almost bipartite

DOI10.1016/J.JCTB.2010.04.004MaRDI QIDQ602711zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Král', Jean-Sébastien Sereni, Michael Stiebitz, Alexandr Kostochka

Publication date 5 November 2010

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

circular coloringodd-girthtree-width

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Abstract: We prove that for every $k$ and every $varepsilon>0$, there exists $g$ such that every graph with tree-width at most $k$ and odd-girth at least $g$ has circular chromatic number at most $2+varepsilon$.

Recommendations

• High-girth graphs avoiding a minor are nearly bipartite
• A note on circular chromatic number of graphs with large girth and similar problems
• The circular chromatic number of series-parallel graphs of large odd girth
• In absence of long chordless cycles, large tree-width becomes a local phenomenon
• Triangle-free graphs of tree-width \(t\) are \(\lceil (t+3)/2 \rceil\)-colorable

Cites work

• (2 + ?)-Coloring of planar graphs with large odd-girth
• 4-chromatic projective graphs
• Circular chromatic number: A survey
• Extending precolorings to circular colorings
• Graph minors. II. Algorithmic aspects of tree-width
• Graph Theory and Probability
• High-girth graphs avoiding a minor are nearly bipartite
• scientific article; zbMATH DE number 4077268 (Why is no real title available?)
• scientific article; zbMATH DE number 932194 (Why is no real title available?)
• Recent developments in circular colouring of graphs
• The circular chromatic number of series-parallel graphs of large odd girth

Cited in

(2)

• In absence of long chordless cycles, large tree-width becomes a local phenomenon
• Graphs of bounded twin-width are quasi-polynomially -bounded

This page was built for publication: Graphs with bounded tree-width and large odd-girth are almost bipartite

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