Title of article
Building blocks for the variety of absolute retracts
Author/Authors
Richard C. Brewster، نويسنده , , Gary MacGillivray، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2006
Pages
7
From page
1758
To page
1764
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
Serial Year
2006
Journal title
Discrete Mathematics
Record number
948018
Link To Document