Retractions of chordal and related graphs
Cynthia Loten · Summit (Simon Fraser University) · 2003
A graph H is a retract of a graph G if H is a subgraph of G and there exists an edge preserving function of the vertex set of G to the vertex set of H that fixes each vertex of H. There are no known necessary and sufficient conditions for H to be a retract of G. We can, however, choose a particular necessary condition, call it N, and study the graphsfor which that particular necessary condition is also sufficient. Such graphs are called absolute retracts with respect to N. A simple necessary condition is preserving distances; this generates the class of absolute retracts with respect to isometry, which has been well studied. Another necessary condition is the following: if there is no vertex in H that is within prescribed distances to a fixed set of vertices of H and H is a retract of G, then there is no such vertex in G either. Thus there is a hole in H that can't be filled by a vertex of G. This is the first necessary condition we explore. There are two other necessary conditions that we study. The former is concerns partial mappings of trees and the latter is based on rephrasing the retraction problem as a list homomorphism problem. These three necessary conditions generate the class of absolute retracts with respect to holes, the class of absolute retracts with respect to tree obstructions, and the class of absolute retracts with respect to arc consistency. We investigate chordal graphs with regard to all three classes of absolute retracts listed above. This leads to the introduction of three classes of graphs that generalize chordal graphs: stretched graphs, strongly stretched graphs, and wheeled graphs. Stretched graphs and strongly stretched graphs are used to characterize the variety generated by chordal graphs, and we prove that wheeled graphs are absolute retracts with respect to arc consistency. We also compare these three classes of absolute retracts with the graphs that admit near unanimity functions and the dismantlable graphs.