Linear bounds on nowhere-zero group irregularity strength and nowhere-zero group sum chromatic number of graphs

DOI10.1016/J.AMC.2018.09.056MaRDI QIDQ2008185zbMATH OpenOpenAlexWikidataFDO

Authors Marcin Anholcer, Sylwia Cichacz, Jakub Przybyło

Publication date 22 November 2019

Published in Applied Mathematics and Computation (Search for Journal in Brave)

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

zbMATH Keywords

abelian grouparboricityirregularity strengthcoloring numbersum chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: We investigate the extit{group irregularity strength}, $s_g(G)$, of a graph, i.e. the least integer $k$ such that taking any Abelian group $mathcalG$ of order $k$, there exists a function $f:E(G)ightarrowmathcalG$ so that the sums of edge labels incident with every vertex are distinct. So far the best upper bound on $s_g(G)$ for a general graph $G$ was exponential in $n-c$, where $n$ is the order of $G$ and $c$ denotes the number of its components. In this note we prove that $s_g(G)$ is linear in $n$, namely not greater than $2n$. In fact, we prove a stronger result, as we additionally forbid the identity element of a group to be an edge label or the sum of labels around a vertex. We consider also locally irregular labelings where we require only sums of adjacent vertices to be distinct. For the corresponding graph invariant we prove the general upper bound: $Delta(G)+mcol(G)-1$ (where $mcol(G)$ is the coloring number of $G$) in the case when we do not use the identity element as an edge label, and a slightly worse one if we additionally forbid it as the sum of labels around a vertex. In the both cases we also provide a sharp upper bound for trees and a constant upper bound for the family of planar graphs.

Recommendations

• Group irregularity strength of connected graphs
• Note on group irregularity strength of disconnected graphs
• Note on the group edge irregularity strength of graphs
• Group irregular labelings of disconnected graphs
• Linear bound on the irregularity strength and the total vertex irregularity strength of graphs

Cites work

• scientific article; zbMATH DE number 4097437 (Why is no real title available?)
• scientific article; zbMATH DE number 867641 (Why is no real title available?)
• A Tight Bound on the Irregularity Strength of Graphs
• A new upper bound for the irregularity strength of graphs
• An iterative approach to graph irregularity strength
• Claw‐decompositions and tutte‐orientations
• Decomposition of Finite Graphs Into Forests
• Degree constrained subgraphs
• Edge weights and vertex colours
• Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties
• Group irregular labelings of disconnected graphs
• Group irregularity strength of connected graphs
• Group sum chromatic number of graphs
• Irregular Assignments of Trees and Forests
• Irregularity strength of trees
• Note on group irregularity strength of disconnected graphs
• Nowhere-zero 6-flows
• Nowhere-zero modular edge-graceful graphs
• On chromatic number of graphs and set-systems
• On modular edge-graceful graphs
• On the irregularity strength of dense graphs
• On vertex-coloring 13-edge-weighting
• The 3-flow conjecture, factors modulo \(k\), and the 1-2-3-conjecture
• Vertex-coloring edge-weightings: towards the 1-2-3-conjecture
• Vertex-colouring edge-weightings

Cited in

(5)

• Group sum chromatic number of graphs
• Group irregularity strength of connected graphs
• Group irregular labelings of disconnected graphs
• Realization of digraphs in Abelian groups and its consequences
• Note on group irregularity strength of disconnected graphs

This page was built for publication: Linear bounds on nowhere-zero group irregularity strength and nowhere-zero group sum chromatic number of graphs

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