On Split B-1-EPG Graphs
Yükleniyor...
Dosyalar
Tarih
2018
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Springer International Publishing Ag
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
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.
Açıklama
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
Anahtar Kelimeler
Kaynak
Latin 2018: Theoretical Informatics
WoS Q Değeri
N/A
Scopus Q Değeri
Q3
Cilt
10807
