Vertex coloring of graphs with few obstructions
type: Item
instance of: scholarly article
title: Vertex coloring of graphs with few obstructions
zbMATH Open document ID: 1350.05038
author: Vadim Lozin
author: D. S. Malyshev
published in: Discrete Applied Mathematics
publication date: 2016-11-24T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6656024
zbMATH Keywords: vertex coloring
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: fixed-parameter tractability
MaRDI profile type: Publication
full work available at URL: j.dam.2015.02.015
OpenAlex ID: W2029256851
cites work: On easy and hard hereditary classes of graphs with respect to the independent set problem
cites work: NP-hard graph problems and boundary classes of graphs
cites work: Boundary classes of graphs for the dominating set problem
cites work: Q3115709
cites work: Approximation algorithms for treewidth
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths
cites work: Graphs with no induced \(C_ 4\) and \(2K_ 2\)
cites work: Clique-width for 4-vertex forbidden subgraphs
cites work: Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
cites work: On diameters and radii of bridged graphs
cites work: 4-coloring \(H\)-free graphs when \(H\) is small
cites work: Parallel concepts in graph theory
cites work: Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
cites work: Improved Complexity Results on k-Coloring P t -Free Graphs
cites work: Q3558598
cites work: The 3-Colorability Problem on Graphs with Maximum Degree Four
cites work: Boundary properties of graphs for algorithmic graph problems
cites work: Q4448764
cites work: On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
cites work: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
cites work: Linear recognition of pseudo-split graphs
cites work: Q3115195
cites work: A study of the boundary graph classes for colorability problems
cites work: On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number
cites work: \(\beta\)-perfect graphs
cites work: 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
cites work: MSOL partitioning problems on graphs of bounded treewidth and clique-width
cites work: Some new hereditary classes where graph coloring remains NP-hard
cites work: A bound on the chromatic number of graphs without certain induced subgraphs
DOI: 10.1016/J.DAM.2015.02.015
description: scientific article; zbMATH DE number 6656024