Coloring Graphs without Short Cycles and Long Induced Paths

This publication has 12 references indexed in Scilit:

• Colouring Vertices of Triangle-Free Graphs
  Lecture Notes in Computer Science, 2010
• Three Complexity Results on Coloring P k -Free Graphs
  Lecture Notes in Computer Science, 2009
• Deciding k-Colorability of P 5-Free Graphs in Polynomial Time
  Algorithmica, 2008
• Vertex Colouring and Forbidden Subgraphs ? A Survey
  Graphs and Combinatorics, 2004
• 3-Colorability ∈P for P6-free graphs
  Discrete Applied Mathematics, 2004
• Triangle-free graphs and forbidden subgraphs
  Discrete Applied Mathematics, 2002
• Complexity of Coloring Graphs without Forbidden Induced Subgraphs
  2001
• Graph colorings with local constraints -- a survey
  Discussiones Mathematicae Graph Theory, 1997
• On the NP-completeness of the k-colorability problem for triangle-free graphs
  Discrete Mathematics, 1996
• The NP-Completeness of Edge-Coloring
  SIAM Journal on Computing, 1981