×

Majority choosability of digraphs. (English) Zbl 1375.05079

Summary: A majority coloring of a digraph is a coloring of its vertices such that for each vertex \(v\), at most half of the out-neighbors of \(v\) have the same color as \(v\). A digraph \(D\) is majority \(k\)-choosable if for any assignment of lists of colors of size \(k\) to the vertices there is a majority coloring of \(D\) from these lists. We prove that every digraph is majority \(4\)-choosable. This gives a positive answer to a question posed recently by S. Kreutzer et al. [ibid. 24, No. 2, Research Paper P2.25, 9 p. (2017; Zbl 1364.05029)]. We obtain this result as a consequence of a more general theorem, in which majority condition is profitably extended. For instance, the theorem implies also that every digraph has a coloring from arbitrary lists of size three, in which at most \(2/3\) of the out-neighbors of any vertex share its color. This solves another problem posed by the same authors, and supports an intriguing conjecture stating that every digraph is majority \(3\)-colorable.

MathOverflow Questions:

Majority coloring for directed graphs

MSC:

05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 1364.05029
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] R. Aharoni, E. C. Milner, K. Prikry, Unfriendly Partitions of a Graph, J. Combin. Theory Ser. B, 50 (1990) 1-10. · Zbl 0717.05065
[2] R. Cowan and W. Emerson, Unfriendly Partitions, Open Problem Garden, (http: //www.openproblemgarden.org/op/unfriendly_partitions).
[3] S. Kreutzer, S. Oum, P. Seymour, D. van der Zypen, D. R. Wood, Majority Colouring of Digraphs, Electron. J. Combin., 24(2) (2017), #P2.25. · Zbl 1364.05029
[4] L. Lov´asz, On decomposition of graphs, Studia Sci. Math. Hungar (1966) 237-238. · Zbl 0151.33401
[5] P. Seymour, On the two-colouring of hypergraphs, Quarterly J. Math., 25 1974, 303-311. · Zbl 0299.05122
[6] S. Shelah, E. C. Milner, Graphs with no unfriendly partitions. A tribute to Paul Erd˝os, 373-384, Cambridge Univ. Press, Cambridge, 1990. · Zbl 0723.05058
[7] D.vanderZypen,Majoritycoloringfordirectedgraphs,2016. MathOverflow(https://mathoverflow.net/questions/233014/ majority-coloring-for-directed-graphs).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.