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

DOI10.1002/JGT.21849MaRDI QIDQ3466342zbMATH OpenOpenAlexFDO

Authors J. Nešetřil, P. Ossona de Mendez

Publication date 1 February 2016

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

nearly bipartite graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

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 $p$th chromatic number $ch{i}_p$, from which follows in particular that graphs $G$ of large girth excluding a minor have $ch{i}_p(G)leqp+2$.

Recommendations

• High-girth graphs avoiding a minor are nearly bipartite
• The circular chromatic number of series-parallel graphs with large girth
• Circular chromatic number of planar graphs of large odd girth
• The circular chromatic index of graphs of high girth
• Homomorphisms from sparse graphs with large girth.

Cites work

• A note on the star chromatic number
• A separator theorem for string graphs and its applications
• Colorings and girth of oriented planar graphs
• Construction of sparse graphs with prescribed circular colorings
• Dense minors in graphs of large girth
• Grad and classes with bounded expansion. I: Decompositions
• High-girth graphs avoiding a minor are nearly bipartite
• Homomorphisms from sparse graphs with large girth.
• Random cubic graphs are not homomorphic to the cycle of size 7
• Small graph classes and bounded expansion
• Tree-depth, subgraph coloring and homomorphism bounds

Cited in

(4)

• Graphs with bounded tree-width and large odd-girth are almost bipartite
• Graphs of large girth with prescribed partial circular colourings
• scientific article; zbMATH DE number 6096704 (Why is no real title available?)
• Box representations of embedded graphs

This page was built for publication: A note on circular chromatic number of graphs with large girth and similar problems

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