A note on circular chromatic number of graphs with large girth and similar problems

2014/02/13 by Jaroslav Nešetřil, Nesetril, Jaroslav, Patrice Ossona de Mendez +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.1402.3142

openalex publication_date 2014/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this short note, we extend the result of Galluccio, Goddyn, and Hell, which states that graphs of large girth excluding a minor are nearly bipartite. We also prove a similar result for the oriented chromatic number, from which follows in particular that graphs of large girth excluding a minor have oriented chromatic number at most 5, and for the pth chromatic number χ_p, from which follows in particular that graphs G of large girth excluding a minor have χ_p(G)≤ p+2.

Related

• Graphs with bounded tree-width and large odd-girth are almost bipartite
• A note on generalized chromatic number and generalized girth
• Two results on the digraph chromatic number
• Geometric graphs with exponential chromatic number and arbitrary girth
• On the odd girth and the circular chromatic number of generalized\n Petersen graphs