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

2009/04/15 by Alexandr Kostochka, Daniel Král͏̌, Kostochka, Alexandr V. +5
Computer Science · Mathematics · #05C15 #05C83 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.0904.2282

openalex publication_date 2009/04/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that for every k and every ε>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+ε.

Related

• A note on circular chromatic number of graphs with large girth and similar problems
• On the odd girth and the circular chromatic number of generalized\n Petersen graphs
• In absence of long chordless cycles, large tree-width becomes a local phenomenon
• Odd coloring graphs with linear neighborhood complexity
• b-coloring graphs with large girth