Reconfiguration of Colorable Sets in Classes of Perfect Graphs
DOI10.4230/LIPICS.SWAT.2018.27zbMATH Open1477.68231OpenAlexW2963009577MaRDI QIDQ5116491FDOQ5116491
Authors: Takehiro Ito, Yota Otachi 
Publication date: 25 August 2020
Full work available at URL: https://dblp.uni-trier.de/db/journals/corr/corr1802.html#abs-1802-06511
Recommendations
- Reconfiguration of colorable sets in classes of perfect graphs
- scientific article; zbMATH DE number 7272506
- The coloring reconfiguration problem on specific graph classes
- scientific article; zbMATH DE number 1944138
- scientific article; zbMATH DE number 863472
- Reconfiguring \(k\)-colourings of complete bipartite graphs
- Colouring Some Classes of Perfect Graphs Robustly
- Perfect colorings of regular graphs
- Set colorings in perfect graphs.
- On the diameter of reconfiguration graphs for vertex colourings
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)
Cites Work
- Geometric algorithms and combinatorial optimization
- Efficient graph representations
- Algorithmic graph theory and perfect graphs
- Incidence matrices and interval graphs
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- On computing longest paths in small graph classes
- Some simplified NP-complete graph problems
- A Characterization of Comparability Graphs and of Interval Graphs
- The complexity of change
- Reconfiguring Independent Sets in Claw-Free Graphs
- Complexity of independent set reconfigurability problems
- On the parameterized complexity of reconfiguration problems
- On the complexity of reconfiguration problems
- Token sliding on chordal graphs
- Linear-time algorithm for sliding tokens on trees
- Parameterized Algorithms for (r,l)-Partization
- Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
- Title not available (Why is that?)
- Title not available (Why is that?)
- LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs
Cited In (4)
This page was built for publication: Reconfiguration of Colorable Sets in Classes of Perfect Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116491)
