Document Type
Lecture
Publication Date
3-20-2024
Abstract
In this talk, we introduce a relation called a vertex contraction-deletion (VCD) minor. A vertex contraction of a vertex v in a graph G is the operation of identifying v and all neighbors of v as a single vertex. A graph H is an VCD minor of a graph G if H can be obtained from G by a sequence of vertex deletions and vertex contractions. This relation lies between that of induced subgraph and induced minor. The definition of VCD minor is motivated by considering definitions of contraction and deletion for hypergraphs that make sense under vertex-edge duality. Representing hypergraphs as bipartite incidence graphs leads to operations for bipartite graphs that can be generalized to all graphs. We prove some basic properties of sequences of vertex contractions and deletions. We show that trees are well-quasi-ordered (WQO) under this relation (like minors and induced minors, unlike induced subgraphs. But since general graphs are not well-quasi-ordered under induced minors, they are not WQO under our relation. Planar graphs have finite characterizations in terms of forbidden substructures under subdivisions, minors and induced minors but not under our relation: we have an infinite antichain of minimal nonplanar graphs. We have also characterized claw-VCD minor-free graphs, which are a subclass of claw-free graphs, by considering claw-VCD minor-free line graphs.
Relational Format
presentation
Recommended Citation
Allred, Sarah, "Vertex Contraction-Deletion Minors" (2024). Combinatorics Seminar. 11.
https://egrove.olemiss.edu/math_combinatorics/11
