A Note on Circular Chromatic Number of Graphs with Large Girth and Similar Problems

DOI10.1002/jgt.21849zbMath1330.05072arXiv1402.3142OpenAlexW1956215601MaRDI QIDQ3466342

Patrice Ossona de Mendez, Jaroslav Nešetřil

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

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

Related Items

Box representations of embedded graphs

Cites Work

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