A unified approach to recognize squares of split graphs

DOI10.1016/J.TCS.2016.07.037MaRDI QIDQ313959zbMATH OpenOpenAlexFDO

Authors Van Bang Le, Andrea Oversberg, Oliver Schaudt

Publication date 12 September 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.07.037

zbMATH Keywords

square of graphssquare of split graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• A good characterization of squares of strongly chordal split graphs
• Bipartite roots of graphs
• scientific article; zbMATH DE number 6469239

Cites work

• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 553916 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• A good characterization of squares of strongly chordal split graphs
• Arboricity, \(h\)-index, and dynamic algorithms
• Complexity aspects of the Helly property: graphs and hypergraphs
• Computing roots of graphs is hard
• Computing square roots of trivially perfect and threshold graphs
• Decomposition of balanced matrices
• Efficient graph representations
• Graph Classes: A Survey
• Hardness Results and Efficient Algorithms for Graph Powers
• On balanced graphs
• Probe threshold and probe trivially perfect graphs
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Split Graphs Having Dilworth Number Two

Cited in

(14)

• A good characterization of squares of strongly chordal split graphs
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• Vertex splitting and the recognition of trapezoid graphs
• Computing square roots of trivially perfect and threshold graphs
• A characterization of line graphs that are squares of graphs
• Characterizing and recognizing exact-distance squares of graphs
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Searching for square-complementary graphs: complexity of recognition and further nonexistence results
• A linear kernel for finding square roots of almost planar graphs
• Finding cactus roots in polynomial time
• Computing square roots of graphs with low maximum degree
• Recognizing Perfect 2-Split Graphs
• A story of diameter, radius, and (almost) Helly property
• Graph square roots of small distance from degree one graphs

This page was built for publication: A unified approach to recognize squares of split graphs

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