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

DOI10.1007/S10878-019-00480-4MaRDI QIDQ2292151zbMATH OpenOpenAlexFDO

Authors Hervé Hocquard, Jakub Przybyło

Publication date 3 February 2020

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

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)

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

Recommendations

• Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree
• On the neighbour sum distinguishing index of graphs with bounded maximum average degree
• Neighbor sum distinguishing total choosability of graphs with larger maximum average degree.
• Neighbor sum distinguishing colorings of graphs with maximum average degree less than \(\frac{37} {12}\)
• Graphs with bounded maximum average degree and their neighbor sum distinguishing total-choice numbers

Cites work

• scientific article; zbMATH DE number 4097437 (Why is no real title available?)
• scientific article; zbMATH DE number 866055 (Why is no real title available?)
• scientific article; zbMATH DE number 867641 (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 bound on the total chromatic number
• A new upper bound for the irregularity strength of graphs
• A note on asymptotically optimal neighbour sum distinguishing colourings
• Asymptotically optimal neighbor sum distinguishing total colorings of graphs
• Combinatorial Nullstellensatz
• How to Define an Irregular Graph
• Irregular Assignments of Trees and Forests
• Irregularity strength of dense graphs
• Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10
• Neighbor sum distinguishing total colorings of \(K_4\)-minor free graphs
• Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree
• Neighbor sum distinguishing total colorings of planar graphs
• Neighbour sum distinguishing total colourings via the combinatorial nullstellensatz
• On graph irregularity strength
• On the irregularity strength of dense graphs
• On the neighbor sum distinguishing index of planar graphs
• On the neighbour sum distinguishing index of graphs with bounded maximum average degree
• On the total-neighbor-distinguishing index by sums
• SOME UNSOLVED PROBLEMS IN GRAPH THEORY

Cited in

(5)

• Graphs with bounded maximum average degree and their neighbor sum distinguishing total-choice numbers
• Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree
• Some bounds on the neighbor-distinguishing index of graphs
• On the neighbour sum distinguishing index of graphs with bounded maximum average degree
• 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)