Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651019 | Discrete Mathematics | 2006 | 7 Pages |
Given a graph H with a labelled subgraph G, a retraction of H to G is a homomorphism r:H→Gr:H→G such that r(x)=xr(x)=x for all vertices x in G. We call G a retract of H. While deciding the existence of a retraction to a fixed graph G is NP-complete in general, necessary and sufficient conditions have been provided for certain classes of graphs in terms of holes, see for example Hell and Rival.For any integer k⩾2k⩾2 we describe a collection of graphs that generate the variety ARkARk of graphs G with the property that G is a retract of H whenever G is a subgraph of H and no hole in G of size at most k is filled by a vertex of H . We also prove that ARk⊂NUFk+1ARk⊂NUFk+1, where NUFk+1NUFk+1 is the variety of graphs that admit a near unanimity function of arity k+1k+1.