Extensional acyclic orientations and set graphs
Presented by Mr. Alexandru I. TOMESCU
Type: Oral presentation
Track: Algorithmic Graph Theory
A graph is said to be a `set graph' if it is the underlying graph of the transitive closure of a hereditarily finite set; equivalently, if it admits an acyclic orientation in which all out-neighborhoods of its vertices are distinct. The study of set graphs was initiated only recently. Even though we argue that recognizing set graphs is NP-complete, we identify, on the one hand, several necessary conditions that every set graph must satisfy. On the other hand, we show that set graphs form a rich class of graphs containing all connected claw-free graphs and all graphs with a Hamiltonian path. In the case of claw-free graphs, we provide a polynomial-time algorithm for finding an extensional acyclic orientation. We also characterize the largest hereditary class in which being connected and claw-free is equivalent to being a set graph.