Partial complementation of graphs

DOI10.4230/LIPICS.SWAT.2018.21zbMATH Open1477.68225OpenAlexW2964088272MaRDI QIDQ5116485FDOQ5116485

Authors: Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Strømme, Dimitrios M. Thilikos 

Publication date: 25 August 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.SWAT.2018.21

Recommendations

• Subgraph complementation
• Energy of partial complements of a graph
• The partial complement of graphs
• Regular-factors in the complements of partial k-trees
• Partitioning a graph into complementary subgraphs

zbMATH Keywords

graph classesgraph editingpartial complementation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Graph structure and monadic second-order logic. A language-theoretic approach
• Recent developments on graphs of bounded clique-width
• Rank-width and vertex-minors
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• List Partitions
• Recognizing locally equivalent graphs
• Finding Branch-Decompositions and Rank-Decompositions
• Title not available (Why is that?)
• Complexity of hypergraph coloring and Seidel's switching.
• Rank-width: algorithmic and structural results
• On Switching to H‐Free Graphs
• Title not available (Why is that?)
• Parameterized problems related to Seidel's switching
• On the hardness of switching to a small number of edges

Cited In (11)

• Title not available (Why is that?)
• Computational graph completion
• Energy of partial complements of a graph
• A survey of parameterized algorithms and the complexity of edge modification
• Title not available (Why is that?)
• The connected component of the partial duplication graph
• Graphs omitting sums of complete graphs
• The partial complement of graphs
• Complement of a graph: a generalization
• Subgraph complementation
• Recognizing some complementary products

This page was built for publication: Partial complementation of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116485)