Yazar "Nivelle, Simon" seçeneğine göre listele

Listeleniyor 1 - 1 / 1
  • Küçük Resim
    Öğe
    On Split B-1-EPG Graphs
    (Springer International Publishing Ag, 2018) Deniz, Zakir; Nivelle, Simon; Ries, Bernard; Schindl, David
    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.