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

DOI10.1002/JGT.21849zbMATH Open1330.05072arXiv1402.3142OpenAlexW1956215601MaRDI QIDQ3466342FDOQ3466342

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)

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$.

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

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.

zbMATH Keywords

nearly bipartite graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Graphs with bounded tree-width and large odd-girth are almost bipartite
• Graphs of large girth with prescribed partial circular colourings
• Title not available (Why is that?)
• 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)