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|
|Date accepted:||No date available|
|Date deposited:||No date available|
|Date of first online publication:||2011|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|