Yazar "Ries, Bernard" seçeneğine göre listele

Listeleniyor 1 - 2 / 2
  • Küçük Resim
    Öğe
    On contact graphs of paths on a grid
    (Springer Verlag, 2018) Deniz, Zakir; Galby, Esther; Munaro, Andrea; Ries, Bernard
    In this paper we consider Contact graphs of Paths on a Grid (CPG graphs), i.e. graphs for which there exists a family of interiorly disjoint paths on a grid in one-to-one correspondence with their vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. Our class generalizes the well studied class of VCPG graphs (see [1]). We examine CPG graphs from a structural point of view which leads to constant upper bounds on the clique number and the chromatic number. Moreover, we investigate the recognition and 3-colorability problems for B0-CPG, a subclass of CPG. We further show that CPG graphs are not necessarily planar and not all planar graphs are CPG. © Springer Nature Switzerland AG 2018.
  • 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.