Szczegóły publikacji
Opis bibliograficzny
Introduction to majority additive coloring / Mateusz KAMYCZURA // Applied Mathematics and Computation ; ISSN 0096-3003. — 2026 — vol. 508 art. no. 129613, s. 1–6. — Bibliogr. s. 5–6, Abstr. — Publikacja dostępna online od: 2025-06-25
Autor
Dane bibliometryczne
| ID BaDAP | 161416 |
|---|---|
| Data dodania do BaDAP | 2025-07-30 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.amc.2025.129613 |
| Rok publikacji | 2026 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Applied Mathematics and Computation |
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.
