Colouring diamond-free graphs
From MaRDI portal
Publication:2402373
DOI10.1016/j.jcss.2017.06.005zbMath1372.05067arXiv1512.07849OpenAlexW2963233231MaRDI QIDQ2402373
François Dross, Daniël Paulusma, Konrad K. Dabrowski
Publication date: 7 September 2017
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1512.07849
Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (18)
Colouring graphs with no induced six-vertex path or diamond ⋮ The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy ⋮ The weighted coloring problem for two graph classes characterized by small forbidden induced structures ⋮ Colouring square-free graphs without long induced paths. ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Clique‐width: Harnessing the power of atoms ⋮ A class of graphs with large rankwidth ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs ⋮ Clique-width and well-quasi-ordering of triangle-free graph classes ⋮ Strong cliques in diamond-free graphs ⋮ Colouring graphs with no induced six-vertex path or diamond ⋮ Colouring square-free graphs without long induced paths ⋮ Tree Pivot-Minors and Linear Rank-Width
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Vertex coloring of graphs with few obstructions
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
- Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
- The coloring problem for classes with two small obstructions
- The behavior of clique-width under graph operations and graph transformations
- Some new hereditary classes where graph coloring remains NP-hard
- Colouring vertices of triangle-free graphs without forests
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Graph classes with and without powers of bounded clique-width
- Classifying the clique-width of \(H\)-free bipartite graphs
- Recent developments on graphs of bounded clique-width
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- Coloring perfect \((K_ 4\)-e)-free graphs
- On (\(P_{5}\), diamond)-free graphs
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- Bipartite graphs without a skew star
- Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
- Edge dominating set and colorings on graphs with fixed clique-width
- Vertex colouring and forbidden subgraphs -- a survey
- Linear time solvable optimization problems on graphs of bounded clique-width
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- Bounding clique-width via perfect graphs
- Clique-width for 4-vertex forbidden subgraphs
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Obstructions for three-coloring graphs with one forbidden induced subgraph
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- Approximating rank-width and clique-width quickly
- ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
- BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION
- Bounding the Clique‐Width of H‐Free Chordal Graphs
- Colouring Diamond-free Graphs.
- GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
- Two cases of polynomial-time solvability for the coloring problem
- Bounding the clique-width of \(H\)-free split graphs
This page was built for publication: Colouring diamond-free graphs
