On Split B-1-EPG Graphs
Loading...
Files
Date
2018
Journal Title
Journal ISSN
Volume Title
Publisher
Springer International Publishing Ag
Access Rights
info:eu-repo/semantics/closedAccess
Abstract
In this paper, we are interested in edge intersection graphs of paths in a grid, such that each such path has at most one bend. These graphs were introduced in [12] and they are called B-1-EPG graphs. In particular, we focus on split graphs and characterise those that are B-1-EPG. This characterisation allows us to disprove a conjecture of Cameron et al. [7]. The existence of polynomial-time recognition algorithm for this graph class is still unknown. We furthermore investigate inclusion relationships among subclasses of split graphs that are B-1-EPG.
Description
13th Latin American Theoretical Informatics Symposium (LATIN) -- APR 16-19, 2018 -- Buenos Aires, ARGENTINA
Schindl, David/0000-0002-7009-5530; Ries, Bernard/0000-0003-4395-5547
WOS: 000444835200027
Schindl, David/0000-0002-7009-5530; Ries, Bernard/0000-0003-4395-5547
WOS: 000444835200027
Keywords
Journal or Series
Latin 2018: Theoretical Informatics
WoS Q Value
N/A
Scopus Q Value
Q3
Volume
10807
