• 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