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

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 $p$th chromatic number $\chi_p$, from which follows in particular that graphs $G$ of large girth excluding a minor have $\chi_p(G)\leq p+2$.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00946134
Author Nesetril, Jaroslav, Ossona de Mendez, Patrice
Maintainer CCSD
Last Updated May 6, 2026, 13:53 (UTC)
Created May 6, 2026, 13:53 (UTC)
Identifier hal-00946134
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Computer Science Institute of Charles University [Prague] (IUUK) ; Univerzita Karlova [Praha, Česká republika] = Charles University [Prague, Czech Republic] = Université Charles [Prague, Republique tchèque] (UK)
creator Nesetril, Jaroslav
date 2014-02-13T00:00:00
harvest_object_id 80773ca6-352c-4d8d-876a-1d8d8d8926e6
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2026-03-12T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/1402.3142
set_spec type:UNDEFINED