A Note on Majority Coloring of Digraphs with Large Indegree

Mengyuan Wang; Shufei Wu

doi:https://doi.org/10.14445/22315373/IJMTT-V69I1P505

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 69 | Issue 1 | Year 2023 | Article Id. IJMTT-V69I1P505 | DOI : https://doi.org/10.14445/22315373/IJMTT-V69I1P505

A Note on Majority Coloring of Digraphs with Large Indegree

Mengyuan Wang, Shufei Wu

Received	Revised	Accepted	Published
23 Nov 2022	28 Dec 2022	06 Jan 2023	18 Jan 2023

Abstract

A majority coloring of a directed graph is a vertex-coloring in which every vertex has the same color as at most half of its out-neighbours. It was conjectured by Kreutzer et al. that every digraph has a majority 3-coloring. This conjecture is far from being resolved. We showed that every digraph D with minimum outdegree at least 28ln|D| has a majority 3-coloring. We also considered the natural generalized 1/k-majority coloring problem.

Keywords

Majority coloring, Chernoff bound, Local lemma.

References

[1] Noga Alon, Jørgen Bang-Jensen, and Stéphane Bessy, “Out-Colorings of Digraphs,” Journal of Graph Theory, vol. 93, no. 1, pp. 88-112.

[2] Xia Weihao et al., “Majority Coloring of R-Regular Digraph,” Chinese Quarterly Journal of Mathematics, vol. 37, no. 2, pp. 142-146, 2022. Crossref, https://doi.org/10.13371/j.cnki.chin.q.j.m.2022.02.004
[3] Michael Anastos et al., “Majority Colorings of Sparse Digraphs,” The Electronic Journal of Combinatorics, vol. 28, no. 2, pp. 1-17, 2021. Crossref, https://doi.org/10.37236/10067
[4] Marcin Anholcer, Bartłomiej Bosek, and Jarosław Grytczuk, “Majority Choosability of Digraphs,” The Electronic Journal of Combinatorics, vol. 24, pp. 1-5, 2017. Crossref, https://doi.org/10.37236/6923
[5] M. Anholcer, B. Bosek, and J. Grytczuk, “Majority Colorings of Infinite Digraphs,” Acta Mathematica Universitatis Comenianae, vol. 88, pp. 371-376, 2019.
[6] M. Anholcer, B. Bosek, and J. Grytczuk, “Majority Choosability of Countable Graphs,” 2020. Crossref, https://arxiv.org/abs/2003.02883
[7] Marcin Anholcer et al., “A Note on Generalized Majority Colorings,” 2022. Crossref, https://doi.org/10.48550/arXiv.2207.09739
[8] József Beck, “An Algorithmic Approach to the LovaSz Local Lemma,” Random Structures and Algorithms, vol. 2, pp. 343-365, 1991. Crossref, https://doi.org/10.1002/rsa.3240020402
[9] Julien Bensmail, Ararat Harutyunyan, and Ngoc Khang Le, “List Coloring Digraphs,” Journal of Graph Theory, vol. 87, no. 4, pp. 492- 508, 2018. Crossref, https://doi.org/10.1002/jgt.22170
[10] BartłomiejBosek, JarosławGrytczuk, and GabrielJakóbczak, “Majority Coloring Game,” Discrete Applied Mathematics, vol. 255, pp. 15- 20, 2019.
[11] O.V.Borodin et al., “Acyclic Coloring of 1-Planar Graphs,” Discrete Applied Mathematics, vol. 114, pp. 29-41, 2001. Crossref, https://doi.org/10.1016/S0166-218X(00)00359-0
[12] Herman Chernoff, “A Note on an Inequality Involving the Normal Distribution,” The Annals of Probability, vol. 9, no. 3, pp. 533-535, 1981. Crossref, https://doi.org/10.1214/aop/1176994428
[13] Guillaume Fertin, André Raspaud, and Bruce Reed, “Star Coloring of Graphs,” Journal of Graph Theory, vol. 47, no. 3, pp. 163-182, 2004.
[14] António Girão, Teeradej Kittipassorn, and kamil Popielarz, “Generalized Majority Colorings of Digraphs,” Combinatorics, Probability and Computing, vol. 26, pp. 850-855, 2017. Crossref, https://doi.org/10.1017/S096354831700044X
[15] J. Haslegrave, “Countable Graphs Are Majority 3-Choosable,” Discussiones Mathematicae Graph Theory, 2021. Crossref, https://doi.org/10.7151/dmgt.2383
[16] G. Jothilakshmi et al., “Distance R-Coloring and Distance R-Dominator Coloring Number of a Graph,” International Journal of Mathematical Trends and Technology, vol. 5, pp. 242-246, 2014. Crossref, https://doi.org/10.14445/22315373/IJMTT-V5P505
[17] Fiachra Knox, and Robert Šámal, “Linear Bound for Majority Colorings of Digraphs,” The Electronic Journal of Combinatorics, vol. 25, no. 3, pp. 1-4, 2018. Crossref, https://doi.org/10.37236/6762
[18] S. Kreutzer et al., “Majority Colorings of Digraphs,” The Electronic Journal of Combinatorics, vol. 24, pp. 1-9, 2017.
[19] Bojan Mohar, “Acyclic Colorings of Locally Planar Graphs,” European Journal of Combinatorics, vol. 26, no. 3-4, pp. 491-503, 2005. Crossref, https://doi.org/10.1016/j.ejc.2003.12.016
[20] Michael Molloy, and Bruce Reed, “Graph Coloring and the Probabilistic Method,” Algorithms and Combinatorics, vol. 23, 2002.
[21] V. Neumann-Lara, “The Dichromatic Number of a Digraph,” Journal of Combinatorial Theory, Series B, vol. 33, no. 3, pp. 265-270, 1982. Crossref, https://doi.org/10.1016/0095-8956(82)90046-6
[22] P. D. Seymour, “On the Two-Coloring of Hypergraphs,” Quarterly Journal of Mathematics, vol. 25, no. 1, pp. 303-311, 1974. Crossref, https://doi.org/10.1093/qmath/25.1.303
[23] R. M. Steiner, “Cycle Structure and Colorings of Directed Graphs,” Technical University Berlin (Germany), 2021.
[24] D. Van Der Zypen, Majority Coloring for Directed Graphs, 2016. [Online]. Available: https://mathoverflow.net/questions/233014/majority-coloring-for-directed-graph

Citation :

Mengyuan Wang, Shufei Wu, "A Note on Majority Coloring of Digraphs with Large Indegree," International Journal of Mathematics Trends and Technology (IJMTT), vol. 69, no. 1, pp. 33-37, 2023. Crossref, https://doi.org/10.14445/22315373/IJMTT-V69I1P505