{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T01:11:21Z","timestamp":1787361081680,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>Let H be a graph and $k \\geq 3$. A near-unanimity function of arity k is a mapping g from the k-tuples over $V(H)$ to $V(H)$ such that $g(x_1, x_2, \\dots, x_k)$ is adjacent to $g(x'_1, x'_2, \\dots, x'_k)$ whenever $x_i x'_i \\in E(H)$ for each $i = 1, 2, \\dots, k$, and $g(x_1, x_2, \\dots, x_k) = a$ whenever at least $k-1$ of the $x_i$'s equal a. Feder and Vardi proved that, if a graph H admits a near-unanimity function, then the homomorphism extension (or retraction) problem for H is polynomial time solvable. We focus on near-unanimity functions on reflexive graphs. The best understood are reflexive chordal graphs H: they always admit a near-unanimity function. We bound the arity of these functions in several ways related to the size of the largest clique and the leafage of H, and we show that these bounds are tight. In particular, it will follow that the arity is bounded by $n -\\sqrt{n}+1$, where $n = |V(H)|$. We investigate substructures forbidden for reflexive graphs that admit a near-unanimity function. It will follow, for instance, that no reflexive cycle of length at least four admits a near-unanimity function of any arity. However, we exhibit nonchordal graphs which do admit near-unanimity functions. Finally, we characterize graphs which admit a conservative near-unanimity function. This characterization has been predicted by the results of Feder, Hell, and Huang. Specifically, those results imply that, if P $\\neq$ NP, the graphs with conservative near-unanimity functions are precisely the so-called bi-arc graphs. We give a proof of this statement without assuming P $\\neq$ NP.<\/jats:p>","DOI":"10.1137\/s0895480103436748","type":"journal-article","created":{"date-parts":[[2008,5,22]],"date-time":"2008-05-22T18:03:46Z","timestamp":1211479426000},"page":"938-960","source":"Crossref","is-referenced-by-count":15,"title":["Near-Unanimity Functions and Varieties of Reflexive Graphs"],"prefix":"10.1137","volume":"22","author":[{"given":"Richard C.","family":"Brewster","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tomas","family":"Feder","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pavol","family":"Hell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gary","family":"MacGillivray","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,5,21]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187059"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90033-C"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90219-E"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.03.036"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"A. A. Bulatov,\n                      Tractable conservative constraint satisfaction problems\n                      , in Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science (Ottawa, Canada, 2003), IEEE Computer Society, Silver Spring, MD, pp. 321\u2013330.","DOI":"10.1109\/LICS.2003.1210072"},{"key":"R6","unstructured":"V. Dalmau and A. Krokhin,\n                      Majority constraints have bounded pathwidth duality\n                      , European J. Combin., to appear."},{"key":"R7","first-page":"97","volume":"26","author":"Dukes P.","year":"1998","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199383353"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1812"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970003"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10073"},{"key":"R12","unstructured":"T. Feder, P. Hell, B. Larose, C. Loten, and C. Tardif,\n                      Near Unanimity Functions and Tree Duals\n                      , manuscript, 2008."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic,\n                      Algorithmic Graph Theory and Perfect Graphs\n                      , Academic Press, New York, 1980.","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"R15","unstructured":"P. Hell,\n                      Retractions de graphes,\n                      Ph.D. thesis, Universit\u00e9 de Montreal, Montreal, Canada, 1972."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"R17","unstructured":"P. Hell and J. Ne\u0161et\u0159il,\n                      Graphs and Homomorphisms\n                      , Oxford Lecture Series in Mathematics and Its Applications 28, Oxford University Press, Oxford, UK, 2004."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-96-01537-1"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1987-025-1"},{"key":"R20","first-page":"297","volume":"33","author":"Huhn A. P.","year":"1972","journal-title":"Acta Sci. Math. (Szeged)"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"E. M. Jawhari, D. Misane, and M. Pouzet,\n                      Retracts: Graphs and ordered sets from the metric point of view\n                      , in Combinatorics and Ordered Sets, Contemp. Math. 57, AMS, Providence, RI, 1986, pp. 175\u2013226.","DOI":"10.1090\/conm\/057\/856237"},{"key":"R22","unstructured":"H. W. Kin and V. Dalmau,\n                      Generalized majority-minority operations are tractable\n                      , in Proceedings of the Twentieth Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society, Washington, DC, 2005, pp. 438\u2013447."},{"key":"R23","unstructured":"G. Kun, B. Larose, and A. Memartolui,\n                      Private communication\n                      , 2004."},{"key":"R24","doi-asserted-by":"crossref","unstructured":"B. Larose, C. Loten, and C. Tardif,\n                      A characterisation of first-order constraint satisfaction problems\n                      , in Proceedings of the 21st IEEE Symposium on Logic in Computer Science, IEEE Computer Society, Washington, DC, 2006, pp. 201\u2013210.","DOI":"10.1109\/LICS.2006.6"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.04.011"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1061"},{"key":"R27","unstructured":"C. Loten,\n                      Retractions of Chordal and Related Graphs\n                      , Ph.D. thesis, Simon Fraser University, Burnaby, BC, Canada, 2003."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90159-0"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90160-7"},{"key":"R30","unstructured":"E. Pesch,\n                      Retracts of Graphs,\n                      Mathematical Systems in Economics 110, Athen\u00e4um, Frankfurt am Main, 1988."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/BF00418652"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480103436748","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:04:56Z","timestamp":1787321096000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480103436748"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/S0895480103436748"],"URL":"https:\/\/doi.org\/10.1137\/s0895480103436748","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}