TY - GEN

T1 - Avoidable vertices and edges in graphs

AU - Beisegel, Jesse

AU - Chudnovsky, Maria

AU - Gurvich, Vladimir

AU - Milanič, Martin

AU - Servatius, Mary

PY - 2019/1/1

Y1 - 2019/1/1

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 -