Upper bounds for adjacent vertex-distinguishing edge coloring
type: Item
instance of: scholarly article
title: Upper bounds for adjacent vertex-distinguishing edge coloring
zbMATH Open document ID: 1392.05046
author: Junlei Zhu
author: Yuehua Bu
author: Yun Dai
published in: Journal of Combinatorial Optimization
publication date: 2018-03-01T00:00:00Z
review text: A proper edge \(k\)-coloring \(f\) of a graph \(G\) is a mapping from the edge set of \(G\) to the set \(\{1, 2, \dots, k\}\) such that no two adjacent edges receive the same color. For a vertex \(v\in V(G)\) let \(F_f(v)\) denote the set of colors of edges incident to \(v\). A proper edge \(k\)-coloring is called an adjacent vertex-distinguishing \(k\)-edge coloring if for every edge \(uv\) in \(G\) is \(F_f(u)\neq F_f(v)\). The smallest \(k\) for which an adjacent vertex-distinguishing edge coloring of \(G\) using \(k\) colors exists is called adjacent vertex-distinguishing chromatic number of \(G\) and is denoted by \(\chi^{'}_{as}(G)\). \textit{Z. Zhang} et al. [Appl. Math. Lett. 15, No. 5, 623--626 (2002; Zbl 1008.05050)] conjectured that for any connected graph \(G\) with at least three vertices different from \(C_5\) is \(\chi^\prime_{as}(G)\leq \Delta(G)+2\). In the given paper, the authors presented an upper bound for this graph parameter and showed that for every connected graph \(G\) with maximum degree \(\Delta(G)\geq 3\) is \(\chi^\prime_{as}(G)\leq 3\Delta(G)-1\). Moreover, they proved that if \(G\) is a graph with maximum degree \(\Delta(G)\geq 458\) and minimum degree \(\delta(G)\geq 8\sqrt{\Delta(G) \ln \Delta(G)}\) then \(\chi^\prime_{as}(G)\leq \Delta(G)+1+5\sqrt{\Delta(G) \ln \Delta(G)}\).
reviewed by: Andrea Semaničová-Feňovčíková
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 6845575
zbMATH Keywords: proper edge coloring
zbMATH Keywords: adjacent vertex-distinguishing edge coloring
zbMATH Keywords: Lovász local lemma
MaRDI profile type: Publication
full work available at URL: s10878-017-0187-0
OpenAlex ID: W2761186239
cites work: \(r\)-strong edge colorings of graphs
cites work: On the Neighbor Sum Distinguishing Index of Planar Graphs
cites work: Vertex-distinguishing proper edge-colorings
cites work: Adjacent Vertex Distinguishing Edge‐Colorings
cites work: Adjacent-vertex-distinguishing proper edge colorings of planar bipartite graphs with \(\Delta=9\), \(10\), or \(11\)
cites work: Q4886768
cites work: On the neighbour-distinguishing index of a graph
cites work: Strong edge colorings of graphs
cites work: Adjacent vertex-distinguishing edge coloring of graphs with maximum degree at least five
cites work: \(\Delta+300\) is a bound on the adjacent vertex distinguishing edge chromatic number
cites work: Adjacent vertex-distinguishing edge coloring of graphs with maximum degree \(\Delta\)
cites work: Q4865126
cites work: Q5312687
cites work: Edge-partitions of graphs and their neighbor-distinguishing index
cites work: Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree
cites work: Adjacent vertex-distinguishing edge colorings of \(K_{4}\)-minor free graphs
cites work: Adjacent vertex-distinguishing edge coloring of 2-degenerate graphs
cites work: Some bounds on the neighbor-distinguishing index of graphs
cites work: Adjacent vertex distinguishing edge colorings of planar graphs with girth at least five
cites work: Adjacent vertex distinguishing colorings by sum of sparse graphs
cites work: Adjacent strong edge coloring of graphs
DOI: 10.1007/S10878-017-0187-0
Recommended article: An improved upper bound on the adjacent vertex distinguishing chromatic index of a graph
Recommended article: On the adjacent vertex-distinguishing total chromatic numbers of the graphs with \(\Delta (G) = 3\)
Recommended article: Adjacent Vertex Distinguishing Edge‐Colorings
Recommended article: Concise proofs for adjacent vertex-distinguishing total colorings
Recommended article: Upper bounds on adjacent vertex distinguishing total chromatic number of graphs
Recommended article: An improved upper bound on the adjacent vertex distinguishing total chromatic number of graphs
Recommended article: A note on the adjacent vertex distinguishing total chromatic number of graphs
Recommended article: Q3193391
Recommended article: An upper bound for the adjacent vertex distinguishing acyclic edge chromatic number of a graph
Recommended article: Q4986030
description: scientific article; zbMATH DE number 6845575