Squares of low clique number

DOI10.1016/j.endm.2016.10.048zbMath1356.05102OpenAlexW2556563262MaRDI QIDQ510991

Dieter Kratsch, Petr A. Golovach, Anthony Stewart, Daniël Paulusma

Publication date: 14 February 2017

Full work available at URL: http://dro.dur.ac.uk/20467/1/20467.pdf

zbMATH Keywords

treewidthsquaresgraph classessquare roots

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

A linear kernel for finding square roots of almost planar graphs ⋮ Computing square roots of graphs with low maximum degree ⋮ Finding cactus roots in polynomial time ⋮ Finding Cactus Roots in Polynomial Time

Cites Work

• A characterization of line graphs that are squares of graphs
• Computing roots of graphs is hard
• A good characterization of squares of strongly chordal split graphs
• Square roots of minor closed graph classes
• Computing square roots of trivially perfect and threshold graphs
• Sparse Square Roots
• 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
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Squares of low clique number