Vertex coloring of graphs with few obstructions

DOI10.1016/J.DAM.2015.02.015zbMATH Open1350.05038OpenAlexW2029256851MaRDI QIDQ344868FDOQ344868

D. S. Malyshev, Vadim Lozin

Publication date: 24 November 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.02.015

zbMATH Keywords

fixed-parameter tractabilitypolynomial-time algorithmvertex coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• 4-coloring \(H\)-free graphs when \(H\) is small
• Boundary classes of graphs for the dominating set problem
• NP-hard graph problems and boundary classes of graphs
• Boundary properties of graphs for algorithmic graph problems
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Approximation algorithms for treewidth
• Parallel concepts in graph theory
• Linear recognition of pseudo-split graphs
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• \(\beta\)-perfect graphs
• Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths
• On diameters and radii of bridged graphs
• Improved Complexity Results on k-Coloring P t -Free Graphs
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• A study of the boundary graph classes for colorability problems
• A bound on the chromatic number of graphs without certain induced subgraphs
• Clique-width for 4-vertex forbidden subgraphs
• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number
• Some new hereditary classes where graph coloring remains NP-hard

Cited In (37)

• Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem
• Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions
• A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
• On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size
• Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes
• The weighted coloring problem for two graph classes characterized by small forbidden induced structures
• The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
• Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs
• Polynomial-time approximation algorithms for the coloring problem in some cases
• Colouring square-free graphs without long induced paths.
• A coloring algorithm for \(4 K_1\)-free line graphs
• Chromatic symmetric functions and \(H\)-free graphs
• On coloring a class of claw-free graphs.
• The intersection of two vertex coloring problems
• Vertex coloring of a graph for memory constrained scenarios
• Colouring square-free graphs without long induced paths
• Colouring diamond-free graphs
• Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
• The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Critical hereditary graph classes: a survey
• Vertex-colored encompassing graphs
• Colouring graphs of bounded diameter in the absence of small cycles
• Colouring graphs of bounded diameter in the absence of small cycles
• A complexity dichotomy and a new boundary class for the dominating set problem
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• On the complexity of colouring antiprismatic graphs
• List coloring in the absence of two subgraphs
• Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
• A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
• Two complexity results for the vertex coloring problem
• On the structure of graphs without claw, \(4K_1\) and co-R
• Two cases of polynomial-time solvability for the coloring problem
• Polynomial cases for the vertex coloring problem
• On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
• $(2P_2,K_4)$-Free Graphs are 4-Colorable

This page was built for publication: Vertex coloring of graphs with few obstructions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344868)