2017/01/31 by António Girão, Teeradej Kittipassorn, Kamil Popielarz · 1 citation
Mathematics · #math.CO #msc:05C15 #msc:05C20
paper · pdf · doi:10.1017/s096354831700044x
published as Combinatorics, Probability and Computing 26 (2017) 850-855 · 4 pages
arxiv created 2018/03/23 · arxiv updated 2018/03/26
The purpose of this note is to draw attention to problems related to a concept called majority colouring recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised a problem of determining, for a natural number k, the smallest number m=m(k) such that every digraph can be coloured with m colours where each vertex has the same colour as at most 1/k proportion of its out-neighbours. We show that m(k)∈\2k-1,2k\. We also prove a result supporting the conjecture that m(2)=3. Moreover, we prove similar results for a more general concept called majority choosability.