Premium
A Note on Circular Chromatic Number of Graphs with Large Girth and Similar Problems
Author(s) -
Nešetřil Jaroslav,
Ossona de Mendez Patrice
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21849
Subject(s) - combinatorics , mathematics , girth (graph theory) , bipartite graph , chromatic scale , odd graph , edge coloring , triangle free graph , discrete mathematics , minor (academic) , graph , chordal graph , 1 planar graph , graph power , line graph , political science , law
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 χ p , from which follows in particular that graphs G of large girth excluding a minor haveχ p ( G ) ≤ p + 2 .
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom