Neighbour sum distinguishing edge-weightings with local constraints

DOI10.1016/J.DAM.2023.04.005MaRDI QIDQ6103480zbMATH OpenOpenAlexFDO

Authors Antoine Dailly, Elżbieta Sidorowicz

Publication date 5 June 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.11521

zbMATH Keywords

1-2-3 conjectureneighbour sum distinguishing edge-colouringneighbour sum distinguishing edge-weighting

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A $k$-edge-weighting of $G$ is a mapping $omega:E(G)longrightarrow1,ldots,k$. The edge-weighting of $G$ naturally induces a vertex-colouring $sigm{a}_{omega}:V(G)longrightarrowmathbbN$ given by$sigm{a}_{omega}(v)=su{m}_{uin{N}_G(v)}omega(vu)$ for every $vinV(G)$. The edge-weighting $omega$ is neighbour sum distinguishing if it yields a proper vertex-colouring $sigm{a}_{omega}$, emph{i.e.}, $sigm{a}_{omega}(u)eqsigm{a}_{omega}(v)$ for every edge $uv$ of $G$.We investigate a neighbour sum distinguishing edge-weighting with local constraints, namely, we assume that the set of edges incident to a vertex of large degree is not monochromatic. A graph is nice if it has no components isomorphic to $K_2$. We prove that every nice graph with maximum degree at most~5 admits a neighbour sum distinguishing $(Delta(G)+2)$-edge-weighting such that all the vertices of degree at least~2 are incident with at least two edges of different weights. Furthermore, we prove that every nice graph admits a neighbour sum distinguishing $7$-edge-weighting such that all the vertices of degree at least~6 are incident with at least two edges of different weights. Finally, we show that nice bipartite graphs admit a neighbour sum distinguishing $6$-edge-weighting such that all the vertices of degree at least~2 are incident with at least two edges of different weights.

Recommendations

• Vertex coloring edge weightings with integer weights at most 6
• Edge weights and vertex colours: minimizing sum count
• Neighbor sum distinguishing index
• scientific article; zbMATH DE number 6613818
• A note on edge weight choosability of graphs

Cites work

• A 1-2-3-4 result for the 1-2-3 conjecture in 5-regular graphs
• A new upper bound for the irregularity strength of graphs
• A note on asymptotically optimal neighbour sum distinguishing colourings
• A relaxed case on 1-2-3 conjecture
• An improved upper bound for the neighbor sum distinguishing index of graphs
• Combinatorial Nullstellensatz
• Edge weights and vertex colours
• Neighbor distinguishing edge colorings via the combinatorial Nullstellensatz
• Neighbor distinguishing edge colorings via the combinatorial Nullstellensatz revisited
• Neighbor sum distinguishing index
• Neighbor-sum-distinguishing edge choosability of subcubic graphs
• On the complexity of vertex-coloring edge-weightings
• The 1-2-3 conjecture almost holds for regular graphs
• The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture
• The neighbour sum distinguishing relaxed edge colouring

Cited in

(4)

• Complexity and algorithms for neighbor-sum-2-distinguishing \(\{1,3\}\)-edge-weighting of graphs
• Edge weights and vertex colours: minimizing sum count
• Vertex coloring edge weightings with integer weights at most 6
• Quasi-majority neighbor sum distinguishing edge-colorings

This page was built for publication: Neighbour sum distinguishing edge-weightings with local constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6103480)