Golovach, P.A. and Paulusma, Daniel and Song, J. (2011) 'Coloring graphs without short cycles and long induced paths.', in Fundamentals of computation theory, 18th International Symposium (FCT 2011), 22-25 August 2011, Oslo, Norway ; proceedings. Berlin: Springer, pp. 193-204. Lecture notes in computer science. (6914).
The girth of a graph G is the length of a shortest cycle in G. For any fixed girth g ≥ 4 we determine a lower bound ℓ(g) such that every graph with girth at least g and with no induced path on ℓ(g) vertices is 3-colorable. In contrast, we show the existence of an integer ℓ such that testing for 4-colorability is NP-complete for graphs with girth 4 and with no induced path on ℓ vertices.
|Item Type:||Book chapter|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-642-22953-4_17|
|Record Created:||03 Jan 2012 15:35|
|Last Modified:||03 Apr 2013 16:18|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|