Reconfiguration of colorable sets in classes of perfect graphs
From MaRDI portal
Publication:2632018
DOI10.1016/j.tcs.2018.11.024zbMath1421.68135arXiv1802.06511OpenAlexW2903402681WikidataQ128820458 ScholiaQ128820458MaRDI QIDQ2632018
Publication date: 17 May 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1802.06511
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Perfect graphs (05C17)
Related Items (3)
Transportation Problem Allowing Sending and Bringing Back ⋮ Token sliding on split graphs ⋮ On reconfigurability of target sets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of rerouting shortest paths
- Complexity of independent set reconfigurability problems
- Linear-time algorithm for sliding tokens on trees
- On the parameterized complexity of reconfiguration problems
- On the complexity of reconfiguration problems
- Approximability of clique transversal in perfect graphs
- The strong perfect graph theorem
- Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
- The maximum k-colorable subgraph problem for chordal graphs
- On chain and antichain families of a partially ordered set
- Generalized vertex covering in interval graphs
- Geometric algorithms and combinatorial optimization
- Some simplified NP-complete graph problems
- The complexity of generalized clique covering
- Efficient graph representations
- Reconfiguration in bounded bandwidth and tree-depth
- Token sliding on chordal graphs
- Algorithmic graph theory and perfect graphs
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- Introduction to reconfiguration
- Incidence matrices and interval graphs
- Normal hypergraphs and the perfect graph conjecture
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
- The complexity of change
- ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
- Reconfiguring Independent Sets in Claw-Free Graphs
- Parameterized Algorithms for (r,l)-Partization
- A Characterization of Comparability Graphs and of Interval Graphs
This page was built for publication: Reconfiguration of colorable sets in classes of perfect graphs
