TY - GEN
T1 - Avoidable vertices and edges in graphs
AU - Beisegel, Jesse
AU - Chudnovsky, Maria
AU - Gurvich, Vladimir
AU - Milanič, Martin
AU - Servatius, Mary
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019
Y1 - 2019
N2 - A vertex v in a graph G is said to be avoidable if every induced two-edge path with midpoint v is contained in an induced cycle. Generalizing Dirac’s theorem on the existence of simplicial vertices in chordal graphs, Ohtsuki et al. proved in 1976 that every graph has an avoidable vertex. In a different generalization, Chvátal et al. gave in 2002 a characterization of graphs without long induced cycles based on the concept of simplicial paths. We introduce the concept of avoidable induced paths as a common generalization of avoidable vertices and simplicial paths. We propose a conjecture that would unify the results of Ohtsuki et al. and of Chvátal et al. The conjecture states that every graph that has an induced k-vertex path also has an avoidable k-vertex path. We prove that every graph with an edge has an avoidable edge, thus establishing the case k= 2 of the conjecture. Furthermore, we point out a close relationship between avoidable vertices in a graph and its minimal triangulations and identify new algorithmic uses of avoidable vertices. More specifically, applying Lexicographic Breadth First Search and bisimplicial elimination orderings, we derive a polynomial-time algorithm for the maximum weight clique problem in a class of graphs generalizing the class of 1-perfectly orientable graphs and its subclasses chordal graphs and circular-arc graphs.
AB - A vertex v in a graph G is said to be avoidable if every induced two-edge path with midpoint v is contained in an induced cycle. Generalizing Dirac’s theorem on the existence of simplicial vertices in chordal graphs, Ohtsuki et al. proved in 1976 that every graph has an avoidable vertex. In a different generalization, Chvátal et al. gave in 2002 a characterization of graphs without long induced cycles based on the concept of simplicial paths. We introduce the concept of avoidable induced paths as a common generalization of avoidable vertices and simplicial paths. We propose a conjecture that would unify the results of Ohtsuki et al. and of Chvátal et al. The conjecture states that every graph that has an induced k-vertex path also has an avoidable k-vertex path. We prove that every graph with an edge has an avoidable edge, thus establishing the case k= 2 of the conjecture. Furthermore, we point out a close relationship between avoidable vertices in a graph and its minimal triangulations and identify new algorithmic uses of avoidable vertices. More specifically, applying Lexicographic Breadth First Search and bisimplicial elimination orderings, we derive a polynomial-time algorithm for the maximum weight clique problem in a class of graphs generalizing the class of 1-perfectly orientable graphs and its subclasses chordal graphs and circular-arc graphs.
UR - http://www.scopus.com/inward/record.url?scp=85070583940&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85070583940&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-24766-9_10
DO - 10.1007/978-3-030-24766-9_10
M3 - Conference contribution
AN - SCOPUS:85070583940
SN - 9783030247652
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 126
EP - 139
BT - Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings
A2 - Friggstad, Zachary
A2 - Salavatipour, Mohammad R.
A2 - Sack, Jörg-Rüdiger
PB - Springer Verlag
T2 - 16th International Symposium on Algorithms and Data Structures, WADS 2019
Y2 - 5 August 2019 through 7 August 2019
ER -