4 papers
Linear Time LexDFS on Chordal Graphs
Jesse Beisegel, Ekkehard Köhler, Robert Scheffler +1
Lexicographic Depth First Search (LexDFS) is a special variant of a Depth First Search (DFS), which was introduced by Corneil and Krueger in 2008. While this search has been used i…
Avoidable Vertices and Edges in Graphs
Jesse Beisegel, Maria Chudnovsky, Vladimir Gurvich +2
A vertex in a graph is simplicial if its neighborhood forms a clique. We consider three generalizations of the concept of simplicial vertices: avoidable vertices (also known as \te…
Recognizing Graph Search Trees
Jesse Beisegel, Carolin Denkert, Ekkehard Köhler +4
Graph searches and the corresponding search trees can exhibit important structural properties and are used in various graph algorithms. The problem of deciding whether a given span…
Characterising AT-free Graphs with BFS
Jesse Beisegel
An asteroidal triple free graph is a graph such that for every independent triple of vertices no path between any two avoids the third. In a recent result from Corneil and Stacho,…