Computing square roots of trivially perfect and threshold graphs

DOI10.1016/j.dam.2012.12.027zbMath1287.05095OpenAlexW1965580387MaRDI QIDQ2446337

Oliver Schaudt, Martin Milanič

Publication date: 16 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.12.027

zbMATH Keywords

split graphchordal graphthreshold graphlinear-time algorithmsquare of a graphtrivially perfect graphsquare root of a graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

A unified approach to recognize squares of split graphs ⋮ A linear kernel for finding square roots of almost planar graphs ⋮ Computing square roots of graphs with low maximum degree ⋮ A characterization of line graphs that are squares of graphs ⋮ Maximizing the strong triadic closure in split graphs and proper interval graphs ⋮ Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs ⋮ Squares of low clique number ⋮ Finding cut-vertices in the square roots of a graph ⋮ Finding cactus roots in polynomial time ⋮ Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 ⋮ A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph ⋮ Graph square roots of small distance from degree one graphs ⋮ Finding Cactus Roots in Polynomial Time ⋮ Unnamed Item ⋮ Parameterized algorithms for finding square roots

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Powers of cycles, powers of paths, and distance graphs
• Uniqueness of graph square roots of girth six
• Hamiltonian cycles in the square of a graph
• A result on the total colouring of powers of cycles
• The square of a block graph
• Coloring the square of the Kneser graph \(\mathrm{KG}(2k+1,k)\) and the Schrijver graph \(\mathrm{SG}(2k+2,k)\)
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Complement reducible graphs
• Trivially perfect graphs
• Computing roots of graphs is hard
• Time bounds for selection
• On the fractional intersection number of a graph
• On uniquely intersectable graphs
• Nowhere-zero 3-flows in squares of graphs
• Algorithmic graph theory and perfect graphs
• Quasi-threshold graphs
• A good characterization of squares of strongly chordal split graphs
• On powers of graphs of bounded NLC-width (clique-width)
• Complexity of finding graph roots with girth conditions
• On a property of the class of n-colorable graphs
• Bipartite roots of graphs
• Large-Girth Roots of Graphs
• List-Coloring Squares of Sparse Subcubic Graphs
• The Comparability Graph of a Tree
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Algorithms for Square Roots of Graphs
• Coloring Powers of Chordal Graphs
• A Note on "The Comparability Graph of a Tree"
• Hardness Results and Efficient Algorithms for Graph Powers

This page was built for publication: Computing square roots of trivially perfect and threshold graphs