A Note on Contractible Edges in Chordal Graphs
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
Contraction of an edge merges its end points into a new vertex which is adjacent to each neighbor of the end points of the edge. An edge in a $k$-connected graph is {\em contractible} if its contraction does not result in a graph of lower connectivity. We characterize contractible edges in chordal graphs using properties of tree decompositions with respect to minimal vertex separators.