Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952525 | Theoretical Computer Science | 2016 | 16 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Van Bang Le, Andrea Oversberg, Oliver Schaudt,