Title of article :
Building blocks for the variety of absolute retracts
Author/Authors :
Richard C. Brewster، نويسنده , , Gary MacGillivray، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2006
Abstract :
Given a graph H with a labelled subgraph G, a retraction of H to G is a homomorphism image such that image 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 image we describe a collection of graphs that generate the variety image 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 image, where image is the variety of graphs that admit a near unanimity function of arity image.
Keywords :
absolute retract , Variety , Near unanimity function
Journal title :
Discrete Mathematics
Journal title :
Discrete Mathematics