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 - Funding Information:
Part of the work for this paper was done in the framework of two bilateral projects between Germany and Slovenia, financed by DAAD and the Slovenian Research Agency (BI-DE/17-19-18 and BI-DE/19-20-04). The third named author was partially funded by Russian Academic Excellence Project ‘5-100’. The work of the fourth named author is supported in part by the Slovenian Research Agency (I0-0035, research program P1-0285 and research projects N1-0032, N1-0102, J1-7051, J1-9110). Part of the work was done while the fourth named author was visiting Osaka Prefecture University in Japan, under the operation Mobility of Slovene higher education teachers 2018–2021, co-financed by the Republic of Slovenia and the European Union under the European Social Fund.
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 -