2025/11/03 by Kalinowski, Rafał, Pilśniak, Monika, Sidorowicz, Elżbieta +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2511.01835
In this paper, a k-edge-coloring of G is any mapping c:E(G)\longrightarrow [k]. The edge-coloring c of G naturally defines a vertex-coloring σc: V(G) → ℕ, where σc(v)=∑u∈ NG(v)c(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, which that σ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 \lceil d(v)/2 \rceil 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.