QUASI-MAJORITY NEIGHBOR SUM DISTINGUISHING EDGE-COLORINGS
2025
Read QUASI-MAJORITY NEIGHBOR SUM DISTINGUISHING EDGE-COLORINGS (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-01835.txt.
Introduction
Rafał Kalinowski, Monika Pilśniak, Elżbieta Sidorowicz, and Elżbieta Turowska color the edges of graphs so that the sums around each vertex identify it. In a neighbor sum distinguishing coloring, each vertex adds up the colors of its incident edges, and neighbors must receive different sums. The authors add a fairness constraint: at every vertex, no single color may cover more than half, rounded up, of its incident edges.
This quasi-majority version has its own index, the fewest colors that suffice. For nice graphs, those without a component that is a single edge, they prove 12 colors always enough. Bipartite graphs need only 6, and graphs whose maximum degree is at most four need only 7, giving concrete universal bounds for a constrained labeling used in network identification problems.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-01835
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
QUASI-MAJORITY NEIGHBOR SUM DISTINGUISHING EDGE-COLORINGS Abstract In this paper, a k k -edge-coloring of G G is any mapping c : E ( G ) ⟶ [ k ] c:E(G)\longrightarrow[k] . The edge-coloring c c of G G naturally defines a vertex-coloring σ c : V ( G ) → ℕ \sigma_{c}:V(G)\to\mathbb{N} , where σ c ( v ) = ∑ u ∈ N G ( v ) c ( v u ) \sigma_{c}(v)=\sum_{u\in N_{G}(v)}c(vu) for every vertex v ∈ V ( G ) v\in V(G) . The edge-coloring c c is said to be neighbor sum distinguishing if it results in a proper vertex-coloring σ c \sigma_{c} , which that σ c ( u ) ≠ σ c ( v ) \sigma_{c}(u)\neq\sigma_{c}(v) for every edge u v uv in G 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 v is incident to at most ⌈ d ( v ) / 2 ⌉ \left\lceil d(v)/2\right\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 K 2 K_{2} . 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 d(v)/2 edges with the same color. Rafał Kalinowski 1 , Monika Pilśniak 1 , Elżbieta Sidorowicz 2 , Elżbieta Turowska 2 1 Department of Discrete Mathematics, AGH University of Krakow, Kraków, Poland 2 Institute of Mathematics, University of Zielona Góra, Zielona Góra, Poland e-mail: [email protected], [email protected], [email protected], [email protected] 1 Introduction We focus on simple, finite graphs. The sets of vertices and edges of a graph G are denoted by V(G) and E(G) , respectively. The term order of G refers to |V(G)| , while size of G refers to |E(G)| . N_{G}(v) ( N(v) for short) denotes the neighborhood of a vertex v in a graph G and d_{G}(v) ( d(v) for short) the degree of a vertex v in a graph G . For any set S\subseteq V(G) , the symbol G[S] denotes the subgraph of G induced by S . Let G_{1} , G_{2} be graphs such that V(G_{1})\cap V(G_{2}) can be nonempty. By G_{1}\cup G_{2} we mean a graph with the vertex set V(G_{1})\cup V(G_{2}) and the edge set E(G_{1})\cup E(G_{2}) . In this paper, a k -edge-coloring of a graph G is any mapping c:E(G)\rightarrow\left[k\right] . Any edge-coloring c induces a vertex-coloring \sigma_{c}:V(G)\rightarrow\mathbb{N} given by \displaystyle\sigma_{c}(v)=\sum_{u\in N(v)}c(vu), for every v\in V(G) . We say that a k -edge-coloring c distinguishes vertices u,v\in V(G) if \sigma_{c}(u)\neq\sigma_{c}(v) . A k -edge-coloring of a graph G is termed neighbor sum distinguishing ( \rm{NSD} for short) if it distinguishes every pair of adjacent vertices, i.e. \sigma_{c} is a proper vertex-coloring of G . The smallest k for which there exists an \rm{NSD} k -edge-coloring of a graph G is called the neighbor sum distinguishing index and is denoted by \chi_{\sum}^{e}(G) . Observe that a graph G always admits an edge-coloring that induces a proper vertex-coloring, except when it includes K_{2} as a component. By assigning a different power of 2 to each edge, we ensure that every vertex receives a distinct sum of colors of incident edges. However, the two vertices of K_{2} cannot be distinguished in this way. Therefore, we call G nice whenever it lacks K_{2} as a component. The concept of coloring edges so that it generates a proper vertex-coloring has been frequently considered, particularly with the emergence of the 1-2-3 Conjecture posed in 2004 by Karoński, Łuczak and Thomason [ 8 ] . To be specific, this hypothesis states that the smallest value of k for which every nice graph G has a k -edge-coloring c such that \sigma_{c}(u)\neq\sigma_{c}(v) for every edge uv\in E(G) is equal to 3. After a series of tens of papers, this conjecture was finally proven by Keusch [ 9 ] . Theorem 1.1 . (Keusch [ 9 ] ) Every nice graph G satisfies \chi_{\sum}^{e}(G)\leq 3 . When we assume the additional restriction that the k -edge-coloring must be proper, then we obtain another version of \rm{NSD} edge-coloring which we call neighbor sum distinguishing proper edge-coloring . The smallest value of k such that such a coloring exists is denoted by \chi^{\prime}_{\sum}(G) . This value is related to a conjecture proposed by Flandrin, Marczyk, Przybyło, Saclé, and Woźniak in [ 5 ] . Conjecture 1.2 . (Flandrin et al. [ 5 ] ) Every nice graph G\neq C_{5} satisfies \chi^{\prime}_{\sum}(G)\leq\Delta(G)+2 . This conjecture remains unresolved. Wang and Yan [ 13 ] showed that \chi^{\prime}_{\sum}(G)\leq\left\lceil(10\Delta(G)+2)/3\right\rceil for graphs with \Delta(G)\geq 18 . Additionally, Przybyło [ 11 ] established that \chi^{\prime}_{\sum}(G)\leq\Delta+O(\sqrt{\Delta}) , where \Delta=\Delta(G) . Let {\rm col}(G) be the coloring number of G , defined as the smallest k such that there is a vertex ordering of G in which each vertex is preceded by at most k-1 of its neighbors. It is known that \chi^{\prime}_{\sum}(G)\leq 2\Delta(G)+{\rm col}(G)-1 [ 10 ] and \chi^{\prime}{\sum}(G)\leq\Delta(G)+3{\rm col}(G)-4 [ 12 ] . Dailly, Duchéne, Parreau, and Sidorowicz in [ 3 ] generalized these conjectures by defining the concept of neighbor sum distinguishing d -relaxed edge-coloring . A k -edge-coloring is d - relaxed if each monochromatic set of edges induces a subgraph with maximum degree at most d . If a d -relaxed k -edge-coloring is distinguishing, then it is called a neighbor sum distinguishing d -relaxed k -edge-coloring . The smallest k for which there is a neighbor sum distinguishing d -relaxed k -edge-coloring of G is denoted by \chi^{\prime d}_{\sum}(G) . Consequently, \chi^{\prime 1}_{\sum}(G)=\chi^{\prime}_{\sum}(G) , and \chi^{\prime\Delta(G)}_{\sum}(G) correspond to the 1-2-3 Conjecture. An approach to investigate graph parameters is to examine bounds on the maximum degree of a graph. While graphs with a maximum degree 2 (which are essentially forests of paths and cycles) are typically straightforward to analyze, the case of subcubic graphs (graphs with a maximum degree 3) often presents more complexity. For example, \chi^{\prime}_{\sum}(G)\leq 6 for every nice subcubic graph G [ 6 ] (the conjecture posits that the bound should be 5). In [ 3 ] , the authors examined the 2-relaxed case for subcubic graphs and proved that \chi^{\prime 2}_{\sum}(G)\leq 4 for every nice graph G with maximum degree at most 3. The paper [ 4 ] by Dailly and Sidorowicz investigates edge-colorings that distinguish vertices and allow