Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time

Haitze J. Broersma, Petr A. Golovach, Daniël Paulusma, Jiupeng Song

Research output: Contribution to journalArticleAcademicpeer-review

21 Citations (Scopus)

Abstract

Let 2P3 denote the disjoint union of two paths on three vertices. A graph G that has no subgraph isomorphic to a graph H is called H-free. The Vertex Coloring problem is the problem to determine the chromatic number of a graph. Its computational complexity for triangle-free H-free graphs has been classified for every fixed graph H on at most 6 vertices except for the case H=2P3. This remaining case is posed as an open problem by Dabrowski, Lozin, Raman and Ries. We solve their open problem by showing polynomial-time solvability.
Original languageUndefined
Pages (from-to)1-10
Number of pages10
JournalTheoretical computer science
Volume423
DOIs
Publication statusPublished - 16 Mar 2012

Keywords

  • Graph coloring
  • Complexity
  • Forbidden subgraphs
  • IR-87792
  • MSC-05C
  • EWI-23727
  • METIS-300016

Cite this