On the total neighbour sum distinguishing index of graphs with bounded maximum average degree

DOI10.1007/S10878-019-00480-4zbMATH Open1434.05053arXiv1803.02686OpenAlexW3123364981MaRDI QIDQ2292151FDOQ2292151

Jakub Przybyło, Hervé Hocquard

Publication date: 3 February 2020

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: A proper total $k$-colouring of a graph $G=(V,E)$ is an assignment $c:VcupEo1,2,ldots,k$ of colours to the edges and the vertices of $G$ such that no two adjacent edges or vertices and no edge and its end-vertices are associated with the same colour. A total neighbour sum distinguishing $k$-colouring, or tnsd $k$-colouring for short, is a proper total $k$-colouring such that $su{m}_{eiu}c(e)+c(u)eqsu{m}_{eiv}c(e)+c(v)$ for every edge $uv$ of $G$. We denote by $ch{i}^{\prime }{\text{'}}_{Sigma}(G)$ the total neighbour sum distinguishing index of $G$, which is the least integer $k$ such that a tnsd edge $k$-colouring of $G$ exists. It has been conjectured that $ch{i}^{\prime }{\text{'}}_{Sigma}(G)leqDelta(G)+3$ for every graph $G$. In this paper we confirm this conjecture for any graph $G$ with $mmad(G)<frac143$ and $Delta(G)geq8$.

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

zbMATH Keywords

combinatorial nullstellensatzdischarging methodmaximum average degreetotal neighbour sum distinguishing index

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Title not available (Why is that?)
• On graph irregularity strength
• Title not available (Why is that?)
• Irregularity strength of dense graphs
• A Tight Bound on the Irregularity Strength of Graphs
• SOME UNSOLVED PROBLEMS IN GRAPH THEORY
• On the total-neighbor-distinguishing index by sums
• Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree
• Neighbor sum distinguishing total colorings of \(K_4\)-minor free graphs
• A New Upper Bound for the Irregularity Strength of Graphs
• Irregular Assignments of Trees and Forests
• Combinatorial Nullstellensatz
• On the Irregularity Strength of Dense Graphs
• Neighbor sum distinguishing total colorings of planar graphs
• Neighbour sum distinguishing total colourings via the combinatorial nullstellensatz
• Title not available (Why is that?)
• A bound on the total chromatic number
• On the Neighbor Sum Distinguishing Index of Planar Graphs
• How to Define an Irregular Graph
• Title not available (Why is that?)
• Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10
• A note on asymptotically optimal neighbour sum distinguishing colourings
• On the neighbour sum distinguishing index of graphs with bounded maximum average degree
• Asymptotically optimal neighbor sum distinguishing total colorings of graphs

Cited In (2)

• Some bounds on the neighbor-distinguishing index of graphs
• Neighbor Sum Distinguishing Total Chromatic Number of Graphs with Lower Average Degree

This page was built for publication: On the total neighbour sum distinguishing index of graphs with bounded maximum average degree

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