Szczegóły publikacji
Opis bibliograficzny
Quasi-majority neighbor sum distinguishing edge-colorings / Rafał KALINOWSKI, Monika PILŚNIAK, Elżbieta Sidorowicz, Elżbieta Turowska // Discrete Mathematics ; ISSN 0012-365X . — 2026 — vol. 349 iss. 10 art. no. 115171, s. 1–17. — Bibliogr. s. 17, Abstr. — Publikacja dostępna online od: 2026-04-20
Autorzy (4)
- AGHKalinowski Rafał
- AGHPilśniak Monika
- Sidorowicz Elżbieta
- Turowska Elżbieta
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 167511 |
|---|---|
| Data dodania do BaDAP | 2026-05-25 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2026.115171 |
| Rok publikacji | 2026 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Mathematics |
Abstract
In this paper, a k -edge-coloring of G is any mapping c:E(G)⟶[k]. The edge-coloring c of G naturally defines a vertex-coloring σc:V(G)→N, where σc(v)=∑uc(vu) for every vertex v∈V(G). The edge-coloring c is said to be neighbor sum distinguishing if it results in a proper vertex-coloring σc, that is, σc(u)≠σc(v) for every edge uv in G . We investigate neighbor sum distinguishing edge-colorings with local constraints, where the edge-coloring is quasi-majority at each vertex. Specifically, every vertex v is incident to at most ⌈d(v)/2⌉ edges of one color. This type of coloring is referred to as quasi-majority neighbor sum distinguishing edge-coloring. The minimum number of colors required for a graph to have a quasi-majority neighbor sum distinguishing edge-coloring is called the quasi-majority neighbor sum distinguishing index. A graph is nice if it has no component isomorphic to K2. We prove that any nice graph admits a quasi-majority neighbor sum distinguishing edge-coloring using at most 12 colors. This bound can be improved for bipartite graphs and graphs with a maximum degree of at most 4. Specifically, we show that every nice bipartite graph can be colored with 6 colors, and every nice graph with a maximum degree of at most 4 can be colored with 7 colors. Additionally, we determine the exact value of the quasi-majority neighbor sum distinguishing index for complete graphs, complete bipartite graphs, and trees. We also consider majority neighbor sum distinguishing edge-colorings, that is, when each vertex is incident to at most d(v)/2 edges with the same color.
