Squares of low clique number

Golovach, P.A.; Kratsch, D.; Paulusma, D.; Stewart, A.

Abstract

The Square Root problem is that of deciding whether a given graph admits a square root. This problem is only known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number of other graph classes. By researching boundedness of the treewidth of a graph, we prove that Square Root is polynomial-time solvable on various graph classes of low clique number that are not minor-closed.

Citation

Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. Squares of low clique number. Presented at 14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW16), Gargnano, Italy

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW16)
• Acceptance Date: Mar 29, 2016
• Online Publication Date: Nov 17, 2016
• Publication Date: Nov 17, 2016
• Deposit Date: Dec 11, 2016
• Publicly Available Date: Nov 17, 2017
• Journal: Electronic Notes in Discrete Mathematics
• Print ISSN: 1571-0653
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 55
• Pages: 195-198
• Series Title: Electronic Notes in Discrete Mathematics
• DOI: https://doi.org/10.1016/j.endm.2016.10.048
• Public URL: https://durham-repository.worktribe.com/output/1148412