Universität zu Köln

Oversberg, Andrea and Schaudt, Oliver (2016). A unified approach to recognize squares of split graphs. Theor. Comput. Sci., 648. S. 26 - 34. AMSTERDAM: ELSEVIER SCIENCE BV. ISSN 1879-2294

Full text not available from this repository.

Abstract

The square of a graph G, denoted by G(2), is obtained from G by putting an edge between two distinct vertices whenever their distance is two. Then G is called a square root of G(2). Deciding whether a given graph has a square root is known to be NP-complete, even if the root is required to be a split graph, that is, a graph in which the vertex set can be partitioned into a stable set and a clique. We give a wide range of polynomial time solvable cases for the problem of recognizing if a given graph is the square of some special kind of split graph. To the best of our knowledge, our result properly contains all previously known such cases. Our polynomial time algorithms are built on a structural investigation of graphs that admit a split square root that is 3-sun-free, and may pave the way toward a dichotomy theorem for recognizing squares of (3-sun-free) split graphs. (C) 2016 Published by Elsevier B.V.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Oversberg, Andrea UNSPECIFIED UNSPECIFIED UNSPECIFIED Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-258597
DOI:	10.1016/j.tcs.2016.07.037
Journal or Publication Title:	Theor. Comput. Sci.
Volume:	648
Page Range:	S. 26 - 34
Date:	2016
Publisher:	ELSEVIER SCIENCE BV
Place of Publication:	AMSTERDAM
ISSN:	1879-2294
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language ROOTS Multiple languages Computer Science, Theory & Methods Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/25859