Golovach, Petr and Kratsch, Dieter and Paulusma, Daniël and Stewart, Anthony (2016) 'Squares of low clique number.', Electronic notes in discrete mathematics., 55 . pp. 195-198.
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.
| Item Type: | Article |
|---|---|
| Full text: | (AM) Accepted Manuscript Available under License - Creative Commons Attribution Non-commercial No Derivatives. Download PDF (266Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.1016/j.endm.2016.10.048 |
| Publisher statement: | © 2016 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/ |
| Date accepted: | 29 March 2016 |
| Date deposited: | 12 December 2016 |
| Date of first online publication: | 17 November 2016 |
| Date first made open access: | 17 May 2018 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
