Partial complementation of graphs

DOI10.4230/LIPICS.SWAT.2018.21MaRDI QIDQ5116485zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(11)

• scientific article; zbMATH DE number 5532174 (Why is no real title available?)
• Computational graph completion
• Energy of partial complements of a graph
• A survey of parameterized algorithms and the complexity of edge modification
• scientific article; zbMATH DE number 6502039 (Why is no real title available?)
• 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)