Skip to main content

Research Repository

Advanced Search

Squares of low clique number

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

Squares of low clique number Thumbnail


Authors

P.A. Golovach

D. Kratsch

A. Stewart



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. (2016). Squares of low clique number. Electronic Notes in Discrete Mathematics, 55, 195-198. https://doi.org/10.1016/j.endm.2016.10.048

Journal Article Type Conference Paper
Conference Name 14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW16)
Conference Location Gargnano, Italy
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

Files





You might also like



Downloadable Citations