List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective
From MaRDI portal
Publication:2234796
DOI10.1016/j.ipl.2021.106168zbMath1476.05050arXiv2008.01590OpenAlexW3122713457MaRDI QIDQ2234796
Daniël Paulusma, Nick Brettell, Jake Horsfield, Andrea Munaro
Publication date: 19 October 2021
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2008.01590
Related Items (5)
Solving problems on generalized convex graphs via mim-width ⋮ Bounding the mim‐width of hereditary graph classes ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph classes with structured neighborhoods and algorithmic applications
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- The behavior of clique-width under graph operations and graph transformations
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Recent developments on graphs of bounded clique-width
- A width parameter useful for chordal and co-comparability graphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Edge dominating set and colorings on graphs with fixed clique-width
- Mim-width. I. Induced path problems
- Colouring \((P_r + P_s)\)-free graphs
- List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
- List 3-coloring graphs with no induced \(P_6 + rP_3\)
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- List coloring in the absence of a linear forest
- Mim-width. II. The feedback vertex set problem
- Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
- Mim-width. III. Graph powers and generalized distance domination problems
- Rank-width: algorithmic and structural results
- Coloring graphs without short cycles and long induced paths
- The point-set embeddability problem for plane graphs
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- The Complexity of Coloring Circular Arcs and Chords
- Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
- More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
- Clique-width for hereditary graph classes
- Hardness of computing width parameters based on branch decompositions over the vertex set
- Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
- Bounding the Mim-Width of Hereditary Graph Classes.
This page was built for publication: List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective
