Article ID Journal Published Year Pages File Type
4651019 Discrete Mathematics 2006 7 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,