Coloring hardness on low twin-width graphs
From MaRDI portal
Cites work
- Achromatic number is NP-complete for cographs and interval graphs
- Complexity Results for Bandwidth Minimization
- Extending partial representations of circular-arc graphs
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- Grid induced minor theorem for graphs of small degree
- Hamilton Paths in Grid Graphs
- Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- On the complexity of k-SAT
- Permutation Graphs and Transitive Graphs
- Planar graph with twin-width seven
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
- Reducibility among combinatorial problems
- Restricted vertex multicut on permutation graphs
- Sparse induced subgraphs of large treewidth
- The firefighter problem for graphs of maximum degree three
- The firefighter problem on graph classes
- Tight lower bounds on graph embedding problems
- Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
- Twin-width and polynomial kernels
- Twin-width II: small classes
- Twin-width of planar graphs is at most 8, and some related bounds
- Twin-width of subdivisions of multigraphs
- Twin-width. I: Tractable FO model checking
- Twin-width. III: Max independent set, min dominating set, and coloring
- Twin-width. VI: The lens of contraction sequences
- Which problems have strongly exponential complexity?
This page was built for publication: Coloring hardness on low twin-width graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7296167)
