Vertex coloring of graphs with few obstructions
From MaRDI portal
(Redirected from Publication:344868)
Recommendations
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- The coloring problem for classes with two small obstructions
- Polynomial cases for the vertex coloring problem
- Polynomial-time approximation algorithms for the coloring problem in some cases
- Coloring graphs characterized by a forbidden subgraph
Cites work
- scientific article; zbMATH DE number 6004968 (Why is no real title available?)
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- 4-coloring \(H\)-free graphs when \(H\) is small
- A bound on the chromatic number of graphs without certain induced subgraphs
- A study of the boundary graph classes for colorability problems
- Approximation algorithms for treewidth
- Boundary classes of graphs for the dominating set problem
- Boundary properties of graphs for algorithmic graph problems
- Clique-width for 4-vertex forbidden subgraphs
- Coloring edges and vertices of graphs without short or long cycles
- Continuous sets of the boundary classes of graphs for coloring problems
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
- Graphs with no induced \(C_ 4\) and \(2K_ 2\)
- Improved complexity results on \(k\)-coloring \(P _{t }\)-free graphs
- Linear recognition of pseudo-split graphs
- Linear time algorithm for computing a small biclique in graphs without long induced paths
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- NP-hard graph problems and boundary classes of graphs
- On diameters and radii of bridged graphs
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- On intersection and symmetric difference of families of boundary classes in the problems on colouring and on the chromatic number
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Parallel concepts in graph theory
- Some new hereditary classes where graph coloring remains NP-hard
- The 3-Colorability Problem on Graphs with Maximum Degree Four
- -perfect graphs
Cited in
(45)- On graphs with no induced P₅ or K₅-e
- 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
- Colouring square-free graphs without long induced paths
- The coloring problem for classes with two small obstructions
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
- The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
- Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Vertex coloring \((4K_1\), hole-twin, 5-wheel)-free graphs
- Polynomial-time approximation algorithms for the coloring problem in some cases
- A coloring algorithm for \(4 K_1\)-free line graphs
- \((2P_2,K_4)\)-free graphs are 4-colorable
- scientific article; zbMATH DE number 3876617 (Why is no real title available?)
- 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
- Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with 5-vertex prohibitions
- Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
- 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
- Critical hereditary graph classes: a survey
- Vertex-colored encompassing graphs
- On graphs without four-vertex induced subgraphs
- A complexity dichotomy and a new boundary class for the dominating set problem
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- Colouring graphs of bounded diameter in the absence of small cycles
- Colouring graphs of bounded diameter in the absence of small cycles
- 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
- On near optimal colorable graphs
- Vertex Coloring of Comparability+ke and –ke Graphs
- 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
- Coloring bridge-free antiprismatic graphs
- 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
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)
