Introduction to majority additive coloring

Mateusz Kamyczura

Applied Mathematics and Computation, 2026, vol. 508, issue C

Abstract: Majority additive coloring is a type of coloring where each vertex is assigned a number, and the sum of its neighbors' numbers, called the neighbor sum, is then computed. For the coloring to be valid, in the neighborhood of each vertex, at most half of its neighbors can share the same neighbor sum. Therefore, majority additive coloring is a combination of two known problems: additive coloring and majority coloring. The majority additive chromatic number, denoted by χmac(G), is the smallest number of colors required to achieve a majority additive coloring of G. We present several results regarding χmac for different types of graphs. For complete graphs and cycles, we have determined the exact value of the parameter, while for trees, we have found a tight upper bound. The main result of this work shows that for graphs with girth greater than 5, a sufficiently large maximum degree, and a minimum degree close to the maximum degree, it is sufficient to use only the numbers 1 and 2.

Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S009630032500339X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:508:y:2026:i:c:s009630032500339x

DOI: 10.1016/j.amc.2025.129613

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().