Avoidable vertices and edges in graphs: existence, characterization, and applications
type: Item
instance of: scholarly article
title: Avoidable vertices and edges in graphs: existence, characterization, and applications
zbMATH Open document ID: 1480.05039
author: Jesse Beisegel
author: Maria Chudnovsky
author: Martin Milanič
author: Mary Servatius
author: Vladimir Gurvich
published in: Discrete Applied Mathematics
publication date: 2022-01-13T00:00:00Z
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 7456401
zbMATH Keywords: avoidable vertex
zbMATH Keywords: avoidable edge
zbMATH Keywords: LBFS
zbMATH Keywords: 1-perfectly orientable graph
zbMATH Keywords: bisimplicial elimination ordering
zbMATH Keywords: maximum weight clique problem
describes a project that uses: House of Graphs
describes a project that uses: CoCalc
MaRDI profile type: Publication
full work available at URL: j.dam.2021.12.006
OpenAlex ID: W4200082749
cites work: Vertex elimination orderings for hereditary graph classes
cites work: In-tournament digraphs
cites work: CLUSTER ALGEBRAS OF FINITE TYPE AND POSITIVE SYMMETRIZABLE MATRICES
cites work: Avoidable vertices and edges in graphs
cites work: Extremities and orderings defined by generalized graph search algorithms
cites work: Graph extremities defined by search algorithms
cites work: Maximum cardinality search for computing minimal triangulations of graphs
cites work: Separability generalizes Dirac's theorem
cites work: AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
cites work: Q4288578
cites work: Avoidable paths in graphs
cites work: Treewidth and minimum fill-in: Grouping the minimal separators
cites work: Listing all potential maximal cliques of a graph
cites work: Graph Classes: A Survey
cites work: 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs
cites work: House of Graphs: a database of interesting graphs
cites work: Dirac-type characterizations of graphs without long chordless cycles
cites work: Treewidth versus clique number in graph classes with a forbidden structure
cites work: Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
cites work: On rigid circuit graphs
cites work: Convexity in Graphs and Hypergraphs
cites work: Large Induced Subgraphs via Triangulations and CMSO
cites work: Finding Induced Subgraphs via Minimal Triangulations
cites work: Incidence matrices and interval graphs
cites work: Algorithmic graph theory and perfect graphs
cites work: Perfect Elimination and Chordal Bipartite Graphs
cites work: On cyclically orientable graphs
cites work: Shifting paths to avoidable ones
cites work: Partial Characterizations of 1‐Perfectly Orientable Graphs
cites work: \(1\)-perfectly orientable graphs and graph products
cites work: Generating weakly triangulated graphs
cites work: Minimal triangulations of graphs: a survey
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: On the semi-perfect elimination
cites work: Approximation algorithms for intersection graphs
cites work: Reducibility among Combinatorial Problems
cites work: A Dirac-type characterization of \(k\)-chordal graphs
cites work: Linear-time recognition of circular-arc graphs
cites work: Q3974692
cites work: Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
cites work: Max flows in O(nm) time, or better
cites work: Characterizations and algorithmic applications of chordal graph embeddings
cites work: Triangulated graphs and the elimination process
cites work: Q5683627
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
cites work: A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
cites work: Efficient graph representations
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: An algorithm for fraternal orientation of graphs
cites work: Q3691771
cites work: Q4869540
cites work: Elimination graphs

Avoidable vertices and edges in graphs: existence, characterization, and applications (DOI)
DOI: 10.1016/J.DAM.2021.12.006