TY - JOUR

T1 - Avoidable vertices and edges in graphs

T2 - Existence, characterization, and applications

AU - Beisegel, Jesse

AU - Chudnovsky, Maria

AU - Gurvich, Vladimir

AU - Milanič, Martin

AU - Servatius, Mary

N1 - Funding Information:
The authors are grateful to the anonymous reviewers for several helpful remarks (in particular, one of the reviewers suggested a short proof of Theorem 3.3 ), to Ekkehard Köhler, Matjaž Krnc, Irena Penev, Robert Scheffler, and Mikhail Vyalyi for interest in our work and valuable discussions, and to Gordon Royle for providing details about Ref. [42] . 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 ), and partly also in the framework of bilateral projects between Slovenia and Russia and between Slovenia and the United States, both partially financed by the Slovenian Research Agency ( BI-RU/19-20-022 and BI-US/19-21-018 ). The work of the third named author was included in the research plan of the International Laboratory of Theoretical Computer Science within the HSE University Basic Research Program . 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 J1-9110, N1-0102, N1-0160). 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 .
Funding Information:
The authors are grateful to the anonymous reviewers for several helpful remarks (in particular, one of the reviewers suggested a short proof of Theorem 3.3), to Ekkehard K?hler, Matja? Krnc, Irena Penev, Robert Scheffler, and Mikhail Vyalyi for interest in our work and valuable discussions, and to Gordon Royle for providing details about Ref. [42]. 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), and partly also in the framework of bilateral projects between Slovenia and Russia and between Slovenia and the United States, both partially financed by the Slovenian Research Agency (BI-RU/19-20-022 and BI-US/19-21-018). The work of the third named author was included in the research plan of the International Laboratory of Theoretical Computer Science within the HSE University Basic Research Program. 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 J1-9110, N1-0102, N1-0160). 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:
© 2021 Elsevier B.V.

PY - 2022/3/15

Y1 - 2022/3/15

N2 - 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 OCF-vertices), simplicial paths, and their common generalization avoidable paths. In an earlier version of this paper, published as an extended abstract in the proceedings of the 16th International Symposium on Algorithms and Data Structures (WADS 2019), we presented a general conjecture on the existence of avoidable paths. The conjecture was recently proved by Bonamy et al. (2020). The conjecture—now a theorem—implies a result due to Ohtsuki, Cheung, and Fujisawa from 1976 on the existence of avoidable vertices and a result due to Chvátal, Sritharan, and Rusu from 2002 on the existence of simplicial paths in graphs excluding all sufficiently long induced cycles. In turn, both of these results generalize Dirac's classical result on the existence of simplicial vertices in chordal graphs. We prove that every graph with at least two edges has two avoidable edges, which strengthens the statement of the theorem of Bonamy et al. for the case of paths of length one. We point out a close relationship between avoidable vertices in a graph and its minimal triangulations, and identify new algorithmic uses of avoidable vertices, leading to new polynomially solvable cases of the maximum weight clique problem in two classes of graphs simultaneously generalizing chordal graphs and circular-arc graphs. Finally, we observe that the results about the existence of avoidable vertices and edges have interesting consequences for highly symmetric graphs: in a vertex-transitive graph every induced two-edge path closes to an induced cycle, while in an edge-transitive graph every three-edge path closes to a cycle and every induced three-edge path closes to an induced cycle.

AB - 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 OCF-vertices), simplicial paths, and their common generalization avoidable paths. In an earlier version of this paper, published as an extended abstract in the proceedings of the 16th International Symposium on Algorithms and Data Structures (WADS 2019), we presented a general conjecture on the existence of avoidable paths. The conjecture was recently proved by Bonamy et al. (2020). The conjecture—now a theorem—implies a result due to Ohtsuki, Cheung, and Fujisawa from 1976 on the existence of avoidable vertices and a result due to Chvátal, Sritharan, and Rusu from 2002 on the existence of simplicial paths in graphs excluding all sufficiently long induced cycles. In turn, both of these results generalize Dirac's classical result on the existence of simplicial vertices in chordal graphs. We prove that every graph with at least two edges has two avoidable edges, which strengthens the statement of the theorem of Bonamy et al. for the case of paths of length one. We point out a close relationship between avoidable vertices in a graph and its minimal triangulations, and identify new algorithmic uses of avoidable vertices, leading to new polynomially solvable cases of the maximum weight clique problem in two classes of graphs simultaneously generalizing chordal graphs and circular-arc graphs. Finally, we observe that the results about the existence of avoidable vertices and edges have interesting consequences for highly symmetric graphs: in a vertex-transitive graph every induced two-edge path closes to an induced cycle, while in an edge-transitive graph every three-edge path closes to a cycle and every induced three-edge path closes to an induced cycle.

KW - 1-perfectly orientable graph

KW - Avoidable edge

KW - Avoidable vertex

KW - Bisimplicial elimination ordering

KW - LBFS

KW - Maximum weight clique problem

UR - http://www.scopus.com/inward/record.url?scp=85121927124&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85121927124&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2021.12.006

DO - 10.1016/j.dam.2021.12.006

M3 - Article

AN - SCOPUS:85121927124

VL - 309

SP - 285

EP - 300

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -