BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T022121Z
UID:Seminar-dept-340@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20140128T160000
DTEND:20140128T170000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Mordo Shalom: Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes\n\nGiven a tree and a set P of non-trivial simple paths on it, VPT(P) is the VPT graph (i.e. the vertex intersection graph) of the paths P, and EPT(P) is the EPT graph (i.e. the edge intersection graph) of P. These graphs have been extensively studied in the literature.\n\nGiven two (edge) intersecting paths in a graph, their split vertices is the set of vertices having degree at least 3 in their union. A pair of (edge) intersecting paths is termed non-splitting if they do not have split vertices (namely if their union is a path).\n\nWe define the graph ENPT(P) of edge intersecting non-splitting paths of a tree, termed the ENPT graph, as the graph having a vertex for each path in P, and an edge between every pair of vertices representing two paths that are both edge-intersecting and non-splitting. A graph G is an ENPT graph if there is a tree T and a set of paths P of T such that G=ENPT(P), and we say that <T,P> is a representation of G.\n\n\n\nOur work follows Golumbic and Jamison's research [GJ85a, GJ85b], in which they defined the EPT graph class, and characterized the representations of chordless cycles (holes). We first show that cycles, trees and complete graphs are ENPT graphs. Our main goal is the characterization of the representations of chordless ENPT cycles. We use the results of [GJ85a,GJ85b] as building blocks in order to discover this characterization, which turn out to have a more complex structure than in the case of EPT holes. To achieve this goal, we first assume that the EPT graph induced by the vertices of an  ENPT hole is given. We introduce three assumptions (P1), (P2), (P3) defined on EPT, ENPT pairs of graphs. We first characterize the representations of ENPT holes that satisfy (P1), (P2), (P3). We then relax two of these three assumptions and characterize the representations of ENPT holes satisfying (P3). These two results are achieved by providing polynomial-time algorithms. Last we show that the problem of finding such a representation is NP-Hard in general, i.e. without assumption (P3). This result extends in some sense the NP-Hardness of EPT graph recognition shown in [GJ85a].\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=340
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR