Coloring graphs without short cycles and long induced paths ?
For an integer k?1 k ? 1 , a graph G G is k k -colorable if there exists a mapping c:VG?{1,,k} c : V G ? { 1 ,  , k } such that c(u)?c(v) c ( u ) ? c ( v ) whenever u u and v v are two adjacent vertices. For a fixed integer k?1 k ? 1 , the k k -Coloring problem is that of testing whether a given graph is k k -colorable. The girth of a graph G G is the length of a shortest cycle in G G . For any fixed g?4 g ? 4 we determine a lower bound ?(g) ? ( g ) , such that every graph with girth at least g g and with no induced path on ?(g) ? ( g ) vertices is 3-colorable. We also show that for all fixed integers k,??1 k , ? ? 1 , thek k -Coloring problem can be solved in polynomial time for graphs with no induced cycle on four vertices and no induced path on ? ? vertices. As a consequence, for all fixed integers k,??1 k , ? ? 1 and g?5 g ? 5 , the k k -Coloring problem can be solved in polynomial time for graphs with girth at least g g and with no induced path on ? ? vertices. This result is best possible, as we prove the existence of an integer ?? ? ? , such that already 4-Coloring is NP-complete for graphs with girth 4 and with no induced path on ?? ? ? vertices.
girth graph coloring forbidden induced subgraph