Graphs admitting k-NU operations. Part 1: The reflexive case

Tomás Feder; Pavol Hell; Benoît Larose; Cynthia Loten; Mark Siggers; Claude Tardif

doi:10.1137/120894312

Graphs admitting k-NU operations. Part 1: The reflexive case

Tomás Feder, Pavol Hell, Benoît Larose, Cynthia Loten, Mark Siggers, Claude Tardif

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

We describe a generating set for the variety of reflexive graphs that admit a compatible k-ary near-unanimity (NU) operation. We further delineate a very simple subset that generates the variety of j-absolute retracts; in particular we show that the class of reflexive graphs with a 4-NU operation coincides with the class of 3-absolute retracts. Our results generalize and encompass several results on NU-graphs and absolute retracts.

Original language	English
Pages (from-to)	1940-1963
Number of pages	24
Journal	SIAM Journal on Discrete Mathematics
Volume	27
Issue number	4
DOIs	https://doi.org/10.1137/120894312
State	Published - 2013

Keywords

Graphs
Near-unanimity operation

Access to Document

10.1137/120894312

Cite this

@article{054f039968584b9d9dc9594cf1bec485,

title = "Graphs admitting k-NU operations. Part 1: The reflexive case",

abstract = "We describe a generating set for the variety of reflexive graphs that admit a compatible k-ary near-unanimity (NU) operation. We further delineate a very simple subset that generates the variety of j-absolute retracts; in particular we show that the class of reflexive graphs with a 4-NU operation coincides with the class of 3-absolute retracts. Our results generalize and encompass several results on NU-graphs and absolute retracts.",

keywords = "Graphs, Near-unanimity operation",

author = "Tom{\'a}s Feder and Pavol Hell and Beno{\^i}t Larose and Cynthia Loten and Mark Siggers and Claude Tardif",

year = "2013",

doi = "10.1137/120894312",

language = "English",

volume = "27",

pages = "1940--1963",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - Graphs admitting k-NU operations. Part 1

T2 - The reflexive case

AU - Feder, Tomás

AU - Hell, Pavol

AU - Larose, Benoît

AU - Loten, Cynthia

AU - Siggers, Mark

AU - Tardif, Claude

PY - 2013

Y1 - 2013

N2 - We describe a generating set for the variety of reflexive graphs that admit a compatible k-ary near-unanimity (NU) operation. We further delineate a very simple subset that generates the variety of j-absolute retracts; in particular we show that the class of reflexive graphs with a 4-NU operation coincides with the class of 3-absolute retracts. Our results generalize and encompass several results on NU-graphs and absolute retracts.

AB - We describe a generating set for the variety of reflexive graphs that admit a compatible k-ary near-unanimity (NU) operation. We further delineate a very simple subset that generates the variety of j-absolute retracts; in particular we show that the class of reflexive graphs with a 4-NU operation coincides with the class of 3-absolute retracts. Our results generalize and encompass several results on NU-graphs and absolute retracts.

KW - Graphs

KW - Near-unanimity operation

UR - http://www.scopus.com/inward/record.url?scp=84891280913&partnerID=8YFLogxK

U2 - 10.1137/120894312

DO - 10.1137/120894312

M3 - Article

AN - SCOPUS:84891280913

SN - 0895-4801

VL - 27

SP - 1940

EP - 1963

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 4

ER -

Graphs admitting k-NU operations. Part 1: The reflexive case

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this