Two cases of polynomial-time solvability for the coloring problem

• Bhattacharya B, Hell P, Huang J (1996) A linear algorithm for maximum weight cliques in proper circular arc graphs. SIAM J Discrete Math 9:274–289

  Article  MathSciNet  MATH  Google Scholar 

• Dabrowski K, Lozin V, Raman R, Ries B (2012) Colouring vertices of triangle-free graphs without forests. Discrete Math 312:1372–1385

  Article  MathSciNet  MATH  Google Scholar 

• Dabrowski K, Golovach P, Paulusma D (2014) Colouring of graphs with Ramsey-type forbidden subgraphs. Theor Comput Sci 522:34–43

  Article  MathSciNet  MATH  Google Scholar 

• Golovach P, Paulusma D (2013) List coloring in the absence of two subgraphs. CIAC, 288–299

• Gyarfas A (1987) Problems from the world surrounding perfect graphs. Zastos Mat Appl Math 3–4:413–441

  MathSciNet  Google Scholar 

• Hoang C, Kaminski M, Lozin V, Sawada J, Shu X (2010) Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time. Algorithmica 57:74–81

  Article  MathSciNet  MATH  Google Scholar 

• Kral’ D, Kratochvil J, Tuza Z, Woeginger G (2001) Complexity of coloring graphs without forbidden induced subgraphs. Lecture Notes in Computer Science, vol 2204. Springer, New York, pp 254–262

• Korpeilainen N, Lozin V, Malyshev D, Tiskin A (2011) Boundary properties of graphs for algorithmic graph problems. Theor Comput Sci 412:3544–3554

  Google Scholar 

• Lin MC, Szwarcfiter JL (2009) Characterizations and recognition of circular-arc graphs and subclasses: a survey. Discrete Math 309:5618–5635

  Article  MathSciNet  MATH  Google Scholar 

• Lozin V, Malyshev D (2014) Vertex coloring of graphs with few obstructions. Discrete Appl Math (accepted)

• Schindl D (2005) Some new hereditary classes where graph coloring remains NP-hard. Discrete Math 295:197–202

  Article  MathSciNet  MATH  Google Scholar 

• Maffray F, Preissmann M (1996) On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs. Discrete Math 162:313–317

  Article  MathSciNet  MATH  Google Scholar 

• Malyshev D (2012) Polynomial solvability of the independent set problem for one class of graphs with small diameter. Diskretnyi Analiz i Issledovanie Operatsii 19(4):66–72 [in Russian]

  MathSciNet  Google Scholar 

• Malyshev D (2014) The coloring problem for classes with two small obstructions. Optim Lett. doi:10.1007/s11590-014-0733-y

• Mycielski J (1955) Sur le coloriage des graphes. Colloq Math 3:161–162

  MathSciNet  MATH  Google Scholar 

Download references