Computing square roots of graphs with low maximum degree

DOI10.1016/j.dam.2017.04.041zbMath1395.05083arXiv1608.06142OpenAlexW2619953306MaRDI QIDQ2413970

Manfred Cochefert, Jean-François Couturier, Daniël Paulusma, Dieter Kratsch, Anthony Stewart, Petr A. Golovach

Publication date: 17 September 2018

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

Full work available at URL: https://arxiv.org/abs/1608.06142

zbMATH Keywords

polynomial algorithmsquare rootbounded degree graph

Mathematics Subject Classification ID

Graph polynomials (05C31) Extremal problems in graph theory (05C35) Vertex degrees (05C07)

Related Items

A linear kernel for finding square roots of almost planar graphs, Finding cactus roots in polynomial time, Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2, Graph square roots of small distance from degree one graphs

Cites Work

• Unnamed Item
• Parameterized algorithms for finding square roots
• A unified approach to recognize squares of split graphs
• A characterization of line graphs that are squares of graphs
• Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs
• Squares of low clique number
• The square of a block graph
• Computing roots of graphs is hard
• A good characterization of squares of strongly chordal split graphs
• Complexity of finding graph roots with girth conditions
• Square roots of minor closed graph classes
• Computing square roots of trivially perfect and threshold graphs
• Finding Cactus Roots in Polynomial Time
• Sparse Square Roots
• Bipartite roots of graphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Algorithms for Square Roots of Graphs
• A Linear Kernel for Finding Square Roots of Almost Planar Graphs
• Parameterized Algorithms
• The square root of a graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth