A good characterization of squares of strongly chordal split graphs

DOI10.1016/J.IPL.2010.11.003MaRDI QIDQ1944051zbMATH OpenOpenAlexFDO

Authors Van Bang Le, Ngoc Tuy Nguyen

Publication date 4 April 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.11.003

zbMATH Keywords

good characterizationsgraph algorithmsgraph powerssquares of split graphsstrongly chordal split graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A unified approach to recognize squares of split graphs
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• The square of a block graph

Cites work

• Characterizations of strongly chordal graphs
• Computing roots of graphs is hard
• Doubly Lexical Orderings of Matrices
• Efficient graph representations
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4077265 (Why is no real title available?)
• scientific article; zbMATH DE number 165077 (Why is no real title available?)
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• The square root of a graph
• Three Partition Refinement Algorithms

Cited in

(17)

• On chordal graph and line graph squares
• Searching for square-complementary graphs: complexity of recognition and further nonexistence results
• Edge ideals of squares of trees
• A linear kernel for finding square roots of almost planar graphs
• Computing square roots of graphs with low maximum degree
• Computing square roots of trivially perfect and threshold graphs
• Parameterized algorithms for finding square roots
• Finding cactus roots in polynomial time
• A unified approach to recognize squares of split graphs
• A characterization of line graphs that are squares of graphs
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Squares of low clique number
• Finding cut-vertices in the square roots of a graph
• Graph square roots of small distance from degree one graphs
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• Finding cactus roots in polynomial time
• The square of a block graph

This page was built for publication: A good characterization of squares of strongly chordal split graphs

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