Publication at Faculty of Mathematics and Physics |
2015
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 pth chromatic number p, from which follows in particular that graphs G of large girth excluding a minor have chi(p)(G) <= p+2. (C) 2014 Wiley Periodicals, Inc.