On the neighbor sum distinguishing index of planar graphs

DOI10.1002/JGT.22098zbMATH Open1367.05066arXiv1408.3190OpenAlexW3121197411MaRDI QIDQ4978296FDOQ4978296

Authors: Marthe Bonamy, Jakub Przybyło 

Publication date: 8 August 2017

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

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$.

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

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

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)

Cites Work

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