Equitable neighbour-sum-distinguishing edge and total colourings

DOI10.1016/J.DAM.2017.01.031MaRDI QIDQ1786869zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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.

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

Cites work

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

Cited in

(8)

• On proper labellings of graphs with minimum label sum
• A notion of vertex equitability for proper labellings
• scientific article; zbMATH DE number 7746013 (Why is no real title available?)
• 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)