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

zbMATH Keywords

perfect graphreconfigurationcolorable set

Mathematics Subject Classification ID

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)

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

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• Algorithmic graph theory and perfect graphs
• Complexity of independent set reconfigurability problems
• Efficient graph representations
• Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
• Geometric algorithms and combinatorial optimization
• Incidence matrices and interval graphs
• LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs
• Linear-time algorithm for sliding tokens on trees
• On computing longest paths in small graph classes
• On the complexity of reconfiguration problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Parameterized algorithms for \((r,l)\)-partization
• Reconfiguring independent sets in claw-free graphs
• Some simplified NP-complete graph problems
• The complexity of change
• The complexity of independent set reconfiguration on bipartite graphs
• Token sliding on chordal graphs
• Universal framework for wireless scheduling problems

Cited in

(8)

• Reconfiguration of cliques in a graph
• The coloring reconfiguration problem on specific graph classes
• Token sliding on split graphs
• Reconfiguration of colorable sets in classes of perfect graphs
• Reconfiguration of cliques in a graph
• Colouring Some Classes of Perfect Graphs Robustly
• Independent set reconfiguration in cographs
• Independent set reconfiguration in cographs and their generalizations

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)