Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
type: Item
instance of: scholarly article
title: Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
zbMATH Open document ID: 1241.05030
author: Petr A. Golovach
author: Daniël Paulusma
author: Jian Song
author: Hajo Broersma
published in: Theoretical Computer Science
publication date: 2012-05-14T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6034854
zbMATH Keywords: chromatic number
zbMATH Keywords: triangle-free
zbMATH Keywords: forbidden induced subgraph
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.12.076
OpenAlex ID: W1982039109
cites work: On graphs with polynomially solvable maximum-weight clique problem
cites work: Triangle-free graphs and forbidden subgraphs
cites work: Three Complexity Results on Coloring P k -Free Graphs
cites work: Updating the complexity status of coloring graphs without a fixed induced linear forest
cites work: A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Colouring Vertices of Triangle-Free Graphs
cites work: The complexity of colouring problems on dense graphs
cites work: Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
cites work: Q3558598
cites work: Q5755526
cites work: Q4448764
cites work: Q4838453
cites work: On the complexity of 4-coloring graphs without long induced paths
cites work: THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
cites work: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
cites work: 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
cites work: Vertex colouring and forbidden subgraphs -- a survey
cites work: A New Algorithm for Generating All the Maximal Independent Sets
cites work: Graph colorings with local constraints -- a survey
cites work: The complexity of coloring graphs without long induced paths
DOI: 10.1016/J.TCS.2011.12.076
description: scientific article; zbMATH DE number 6034854