Equitable neighbour-sum-distinguishing edge and total colourings

DOI10.1016/J.DAM.2017.01.031zbMATH Open1396.05037arXiv1701.04648OpenAlexW2412010298MaRDI QIDQ1786869FDOQ1786869

Authors: Olivier Baudon, Monika Pilśniak, Jakub Przybyło, Mohammed Senhaji, Mariusz Woźniak, Éric Sopena 

Publication date: 25 September 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: With any (not necessarily proper) edge $k$-colouring $gamma:E(G)longrightarrow1,dots,k$ of a graph $G$,one can associate a vertex colouring $sigm{a}_{gamma}$ given by $sigm{a}_{gamma}(v)=su{m}_{eiv}gamma(e)$.A neighbour-sum-distinguishing edge $k$-colouring is an edge colouring whose associated vertex colouring is proper.The neighbour-sum-distinguishing index of a graph $G$ is then the smallest $k$ for which $G$ admitsa neighbour-sum-distinguishing edge $k$-colouring.These notions naturally extends to total colourings of graphs that assign colours to both vertices and edges.We study in this paper equitable neighbour-sum-distinguishing edge colourings andtotal colourings, that is colourings $gamma$ for whichthe number of elements in any two colour classes of $gamma$ differ by at most one.We determine the equitable neighbour-sum-distinguishing indexof complete graphs, complete bipartite graphs and forests,and the equitable neighbour-sum-distinguishing total chromatic numberof complete graphs and bipartite graphs.

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

Recommendations

• scientific article; zbMATH DE number 7746013
• On the vertex distinguishing equitable edge-coloring of graphs
• On the adjacent vertex-distinguishing equitable edge coloring of graphs
• The neighbour sum distinguishing relaxed edge colouring
• scientific article; zbMATH DE number 6470667
• Neighbor sum distinguishing total colorings of planar graphs
• Neighbor sum distinguishing edge coloring of subcubic graphs
• Equitable edge-colorings of simple graphs
• Neighbor sum distinguishing coloring of some graphs
• Neighbour sum distinguishing total colourings via the combinatorial nullstellensatz

zbMATH Keywords

equitable colouringneighbour-sum-distinguishing edge colouringneighbour-sum-distinguishing total colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Title not available (Why is that?)
• On vertex-coloring 13-edge-weighting
• Edge weights and vertex colours
• Vertex-colouring edge-weightings
• Degree constrained subgraphs
• On a \(1,2\) conjecture
• Handbook of combinatorial optimization. In 5 volumes
• Vertex-coloring edge-weightings: towards the 1-2-3-conjecture
• Vertex-colouring edge-weightings with two edge weights
• Vertex-coloring edge-weightings of graphs

Cited In (8)

• On proper labellings of graphs with minimum label sum
• A notion of vertex equitability for proper labellings
• Title not available (Why is that?)
• Further results on an equitable 1-2-3 conjecture
• On Proper Labellings of Graphs with Minimum Label Sum
• A note on neighbor expanded sum distinguishing index
• On the role of 3s for the 1-2-3 conjecture
• The neighbour-sum-distinguishing edge-colouring game

This page was built for publication: Equitable neighbour-sum-distinguishing edge and total colourings

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