{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T15:35:50Z","timestamp":1775835350218,"version":"3.50.1"},"reference-count":6,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2017,8,14]],"date-time":"2017-08-14T00:00:00Z","timestamp":1502668800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2017,11]]},"abstract":"<jats:p>We almost completely solve a number of problems related to a concept called majority colouring recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised the problem of determining, for a natural number<jats:italic>k<\/jats:italic>, the smallest number<jats:italic>m<\/jats:italic>=<jats:italic>m<\/jats:italic>(<jats:italic>k<\/jats:italic>) such that every digraph can be coloured with<jats:italic>m<\/jats:italic>colours where each vertex has the same colour as at most a 1\/<jats:italic>k<\/jats:italic>proportion of its out-neighbours. We show that<jats:italic>m<\/jats:italic>(<jats:italic>k<\/jats:italic>) \u2208 {2<jats:italic>k<\/jats:italic>\u2212 1,2<jats:italic>k<\/jats:italic>}. We also prove a result supporting the conjecture that<jats:italic>m<\/jats:italic>(2) = 3. Moreover, we prove similar results for a more general concept called majority choosability.<\/jats:p>","DOI":"10.1017\/s096354831700044x","type":"journal-article","created":{"date-parts":[[2017,8,14]],"date-time":"2017-08-14T02:29:38Z","timestamp":1502677778000},"page":"850-855","source":"Crossref","is-referenced-by-count":7,"title":["Generalized Majority Colourings of Digraphs"],"prefix":"10.1017","volume":"26","author":[{"given":"ANT\u00d3NIO","family":"GIR\u00c3O","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TEERADEJ","family":"KITTIPASSORN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KAMIL","family":"POPIELARZ","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2017,8,14]]},"reference":[{"key":"S096354831700044X_ref3","first-page":"61","volume-title":"Analysis at Urbana, Vol. II (Urbana, IL, 1986\u20131987)","author":"Bourgain","year":"1989"},{"key":"S096354831700044X_ref4","unstructured":"GLPK: GNU Linear Programming Kit. https:\/\/www.gnu.org\/software\/glpk\/"},{"key":"S096354831700044X_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306008042"},{"key":"S096354831700044X_ref5","unstructured":"Knox F. and \u0160\u00e1mal R. (2017) Linear bound for majority colourings of digraphs. arXiv:1701.05715"},{"key":"S096354831700044X_ref2","unstructured":"Anholcer M. , Bosek B. and Grytczuk J. (2016) Majority choosability of digraphs. arXiv:1608.06912"},{"key":"S096354831700044X_ref6","doi-asserted-by":"crossref","DOI":"10.37236\/6410","article-title":"Majority colourings of digraphs","volume":"24","author":"Kreutzer","year":"2017","journal-title":"Electron. J. Combin."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831700044X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T04:40:41Z","timestamp":1602736841000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831700044X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,14]]},"references-count":6,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["S096354831700044X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831700044x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,14]]}}}