Vertex coloring of graphs with few obstructions
From MaRDI portal
Publication:344868
DOI10.1016/j.dam.2015.02.015zbMath1350.05038MaRDI QIDQ344868
Vadim V. Lozin, Dmitriy S. Malyshev
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
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size, $(2P_2,K_4)$-Free Graphs are 4-Colorable, Two cases of polynomial-time solvability for the coloring problem, Colouring graphs of bounded diameter in the absence of small cycles, A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs, A complexity dichotomy and a new boundary class for the dominating set problem, Two complexity results for the vertex coloring problem, Critical hereditary graph classes: a survey, Polynomial cases for the vertex coloring problem, The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable, The weighted coloring problem for two graph classes characterized by small forbidden induced structures, A coloring algorithm for \(4 K_1\)-free line graphs, On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs, The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs, Chromatic symmetric functions and \(H\)-free graphs, Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs, On coloring a class of claw-free graphs., Vertex coloring of a graph for memory constrained scenarios, The intersection of two vertex coloring problems, Colouring square-free graphs without long induced paths, The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs, Polynomial-time approximation algorithms for the coloring problem in some cases, 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, List coloring in the absence of two subgraphs, On the complexity of colouring antiprismatic graphs, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
- Boundary properties of graphs for algorithmic graph problems
- Some new hereditary classes where graph coloring remains NP-hard
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Approximation algorithms for treewidth
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- On diameters and radii of bridged graphs
- A bound on the chromatic number of graphs without certain induced subgraphs
- Parallel concepts in graph theory
- Linear recognition of pseudo-split graphs
- 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
- Graphs with no induced \(C_ 4\) and \(2K_ 2\)
- Boundary classes of graphs for the dominating set problem
- \(\beta\)-perfect graphs
- Clique-width for 4-vertex forbidden subgraphs
- NP-hard graph problems and boundary classes of graphs
- Improved Complexity Results on k-Coloring P t -Free Graphs
- Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths
- 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
- A study of the boundary graph classes for colorability problems