On the neighbor sum distinguishing index of planar graphs

DOI10.1002/JGT.22098MaRDI QIDQ4978296zbMATH OpenOpenAlexFDO

Authors Marthe Bonamy, Jakub Przybyło

Publication date 8 August 2017

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

1-2-3 conjecturedischarging methodneighbor sum distinguishing indexadjacent strong chromatic index

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)

Abstract: Let $c$ be a proper edge colouring of a graph $G=(V,E)$ with integers $1,2,ldots,k$. Then $kgeqDelta(G)$, while by Vizing's theorem, no more than $k=Delta(G)+1$ is necessary for constructing such $c$. On the course of investigating irregularities in graphs, it has been moreover conjectured that only slightly larger $k$, i.e., $k=Delta(G)+2$ enables enforcing additional strong feature of $c$, namely that it attributes distinct sums of incident colours to adjacent vertices in $G$ if only this graph has no isolated edges and is not isomorphic to $C_5$. We prove the conjecture is valid for planar graphs of sufficiently large maximum degree. In fact even stronger statement holds, as the necessary number of colours stemming from the result of Vizing is proved to be sufficient for this family of graphs. Specifically, our main result states that every planar graph $G$ of maximum degree at least $28$ which contains no isolated edges admits a proper edge colouring $c:Eo1,2,ldots,Delta(G)+1$ such that $su{m}_{eiu}c(e)eqsu{m}_{eiv}c(e)$ for every edge $uv$ of $G$.

Recommendations

• Neighbor sum distinguishing index of planar graphs
• On the neighbor sum distinguishing total coloring of planar graphs
• On Neighbor-Distinguishing Index of Planar Graphs
• Neighbor sum distinguishing total colorings of planar graphs
• On generalized neighbor sum distinguishing index of planar graphs

Cites work

• scientific article; zbMATH DE number 4097437 (Why is no real title available?)
• scientific article; zbMATH DE number 6303005 (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
• Adjacent Vertex Distinguishing Edge‐Colorings
• Adjacent strong edge coloring of graphs
• Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree
• Adjacent vertex-distinguishing edge coloring of graphs with maximum degree
• An improved upper bound for the neighbor sum distinguishing index of graphs
• Asymptotically optimal neighbour sum distinguishing colourings of graphs
• Combinatorial Nullstellensatz
• Degree constrained subgraphs
• Distant irregularity strength of graphs
• Edge weights and vertex colours
• How to Define an Irregular Graph
• Irregular Assignments of Trees and Forests
• Irregularity strength of dense graphs
• Linear bound on the irregularity strength and the total vertex irregularity strength of graphs
• Neighbor distinguishing edge colorings via the combinatorial Nullstellensatz
• Neighbor distinguishing edge colorings via the combinatorial Nullstellensatz revisited
• Neighbor sum distinguishing coloring of some graphs
• Neighbor sum distinguishing index
• Neighbor sum distinguishing index of planar graphs
• Neighbour-distinguishing edge colourings of random regular graphs
• On Neighbor-Distinguishing Index of Planar Graphs
• On graph irregularity strength
• On the irregularity strength of dense graphs
• On the irregularity strength of trees
• On vertex-coloring 13-edge-weighting
• Vertex-coloring edge-weightings: towards the 1-2-3-conjecture
• Vertex-colouring edge-weightings
• \(\Delta+300\) is a bound on the adjacent vertex distinguishing edge chromatic number
• r-strong edge colorings of graphs

Cited in

(29)

• Neighbor sum distinguishing colorings of graphs with maximum average degree less than \(\frac{37} {12}\)
• The adjacent vertex distinguishing edge choosability of planar graphs with maximum degree at least 11
• Neighbor sum distinguishing index of \(K_4\)-minor free graphs
• Neighbor sum distinguishing index of 2-degenerate graphs
• Progress on the adjacent vertex distinguishing edge coloring conjecture
• Distant sum distinguishing index of graphs
• Neighbor sum distinguishing index of subcubic graphs
• Neighbor sum distinguishing index of planar graphs
• Neighbor sum distinguishing edge colorings of sparse graphs
• Distant sum distinguishing index of graphs with bounded minimum degree
• Neighbor sum distinguishing index of sparse graphs
• An improved upper bound for neighbor sum distinguishing edge colorings of graphs
• A note on asymptotically optimal neighbour sum distinguishing colourings
• Neighbor sum distinguishing total chromatic number of 2-degenerate graphs
• Adjacent vertex distinguishing edge choosability of 1-planar graphs with maximum degree at least 23
• On Neighbor-Distinguishing Index of Planar Graphs
• Neighbour sum distinguishing total colourings via the combinatorial nullstellensatz
• Asymptotic confirmation of the Faudree–Lehel conjecture on irregularity strength for all but extreme degrees
• Distant set distinguishing edge colourings of graphs
• Neighbor sum distinguishing chromatic index of sparse graphs via the combinatorial Nullstellensatz
• Neighbor-sum-distinguishing edge choosability of subcubic graphs
• On the total neighbour sum distinguishing index of graphs with bounded maximum average degree
• List neighbor sum distinguishing edge coloring of subcubic graphs
• Adjacent vertex distinguishing colorings by sum of sparse graphs
• On generalized neighbor sum distinguishing index of planar graphs
• On the neighbour sum distinguishing index of graphs with bounded maximum average degree
• Upper bounds for adjacent vertex-distinguishing edge coloring
• Improved bounds for neighbor sum (set) distinguishing choosability of planar graphs
• Neighbor sum distinguishing edge coloring of subcubic graphs

This page was built for publication: On the neighbor sum distinguishing index of planar graphs

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