{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:43:30Z","timestamp":1787323410344,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>Brooks proved that every connected graph other than a clique or odd cycle can be colored with $\\Delta$ colors. Erd\u0151s, Rubin, and Taylor (and, independently, Vizing) generalized the theorem of Brooks to list colorings, describing all uncolorable connected graphs in which no vertex has a list smaller than its degree. Other authors have extended this to list T-colorings and their generalizations. We further extend it to model pair-list colorings. In addition to including all of the previous situations, pair-list colorings also generalize list homomorphisms (also known as list H-colorings). In the general context of pair-list colorings, we prove a Brooks-type theorem which extends many (but not all) of the existing results. Our result applies to both graphs and digraphs, with or without loops. We discuss several applications of the result, including a polynomial test for the existence of balanced list homomorphisms and retractions.<\/jats:p>","DOI":"10.1137\/06066000x","type":"journal-article","created":{"date-parts":[[2008,2,7]],"date-time":"2008-02-07T12:09:46Z","timestamp":1202386186000},"page":"1-14","source":"Crossref","is-referenced-by-count":2,"title":["Brooks-Type Theorems for Pair-List Colorings and List Homomorphisms"],"prefix":"10.1137","volume":"22","author":[{"given":"Tom\u00e1s","family":"Feder","sequence":"first","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"}]}],"member":"351","published-online":{"date-parts":[[2008,2,6]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00124-8"},{"key":"R2","unstructured":"B. Bollob\u00e1s,\n                      Extremal Graph Theory\n                      , Academic Press, New York, 1978."},{"key":"R3","unstructured":"O. V. Borodin,\n                      Criterion of chromaticity of a degree prescription\n                      , in Abstracts of the 4th All-Union Conference on Theoretical Cybernetics, Novosibirsk, 1977, pp. 127\u2013128."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1016"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410002168X"},{"key":"R6","unstructured":"P. Erd\u0151s, A. L. Rubin, and H. Taylor,\n                      Choosability in graphs\n                      , in Proceedings of the West Coast Conference on Combinatorics, Graph Theory, and Computing, Congress. Numer. XXVI, Utilitas Math., Winnipeg, MB, 1980, pp. 125\u2013157."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1812"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970003"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10073"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.09.030"},{"key":"R11","unstructured":"T. Feder, P. Hell, and J. Huang,\n                      Extension problems with degree bounds\n                      , submitted."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103437870"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00009-1"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"P. Hell and J. Ne\u0161et\u0159il,\n                      Counting list homomorphisms and graphs with bounded degrees\n                      , in Graphs, Morphisms and Statistical Physics, J. Ne\u0161et\u0159il and P. Winkler, eds., DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 63, AMS, Providence, RI, 2004, pp. 105\u2013112.","DOI":"10.1090\/dimacs\/063\/08"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"P. Hell and J. Ne\u0161et\u0159il,\n                      Graphs and Homomorphisms\n                      , Oxford University Press, Oxford, UK, 2004.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00294-7"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199707)25:3<207::AID-JGT4>3.0.CO;2-P"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90150-3"},{"key":"R21","first-page":"3","volume":"29","author":"Vizing V. G.","year":"1976","journal-title":"Diskret. Analiz."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/28.4.337"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/06066000X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:01:00Z","timestamp":1787320860000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/06066000X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/06066000X"],"URL":"https:\/\/doi.org\/10.1137\/06066000x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}