An improved upper bound on the adjacent vertex distinguishing chromatic index of a graph

DOI10.1016/J.DAM.2013.08.038zbMATH Open1300.05112arXiv1208.2315OpenAlexW2101259320MaRDI QIDQ741759FDOQ741759

Authors: Ko-Wei Lih, Lianzhu Zhang, Weifan Wang 

Publication date: 12 September 2014

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

Abstract: An adjacent vertex distinguishing coloring of a graph G is a proper edge coloring of G such that any pair of adjacent vertices are incident with distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing coloring of G is denoted by $chi{\text{'}}_a(G)$. In this paper, we prove that $ch{i_a}^{\prime }(G)$ <= 5($Delta+2$)/2 for any graph G having maximum degree $Delta$ and no isolated edges. This improves a result in [S. Akbari, H. Bidkhori, N. Nosrati, r-Strong edge colorings of graphs, Discrete Math. 306 (2006), 3005-3010], which states that $ch{i_a}^{\prime }(G)$ <= 3$Delta$ for any graph G without isolated edges.

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

Recommendations

• Upper bounds for adjacent vertex-distinguishing edge coloring
• An improved upper bound on the adjacent vertex distinguishing edge chromatic number of a simple graph.
• An improved upper bound on the adjacent vertex distinguishing total chromatic number of graphs
• Adjacent vertex distinguishing index of graphs with maximum degree six
• Adjacent Vertex Distinguishing Edge‐Colorings

zbMATH Keywords

maximum degreeadjacent vertex distinguishing coloringedge-partition

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Adjacent strong edge coloring of graphs
• Vertex distinguishing colorings of graphs with \(\Delta(G)=2\)
• Vertex-distinguishing proper edge-colorings
• On the vertex-distinguishing proper edge-colorings of graphs
• \(\Delta+300\) is a bound on the adjacent vertex distinguishing edge chromatic number
• Adjacent Vertex Distinguishing Edge‐Colorings
• \(r\)-strong edge colorings of graphs
• Balanced edge colorings.
• Vertex‐distinguishing edge colorings of random graphs
• Title not available (Why is that?)
• A note on the vertex-distinguishing proper coloring of graphs with large minimum degree
• Vertex-distinguishing edge colorings of graphs
• Title not available (Why is that?)
• Adjacent vertex-distinguishing edge coloring of graphs with maximum degree at least five
• Adjacent vertex-distinguishing edge coloring of graphs with maximum degree \(\Delta\)
• Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree
• On the neighbour-distinguishing index of a graph
• Adjacent vertex-distinguishing edge colorings of \(K_{4}\)-minor free graphs
• Vertex-distinguishing edge colorings of graphs with degree sum conditions

Cited In (23)

• An upper bound for the adjacent vertex distinguishing acyclic edge chromatic number of a graph
• Progress on the adjacent vertex distinguishing edge coloring conjecture
• On the neighbor-distinguishing indices of planar graphs
• Neighbor sum distinguishing index of subcubic graphs
• Title not available (Why is that?)
• Adjacent Vertex Distinguishing Edge‐Colorings
• Title not available (Why is that?)
• Adjacent vertex distinguishing index of graphs with maximum degree six
• The algorithm for adjacent vertex distinguishing proper edge coloring of graphs
• Two-distance vertex-distinguishing index of sparse graphs
• Two-distance vertex-distinguishing index of sparse subcubic graphs
• On the inclusion chromatic index of a Halin graph
• Edge-partitions of graphs and their neighbor-distinguishing index
• Some bounds on the neighbor-distinguishing index of graphs
• Strict neighbor-distinguishing index of subcubic graphs
• Fractional chromatic number of adjacent-vertex distinguishing edge coloring
• Neighbor-distinguishing indices of planar graphs with maximum degree ten
• Title not available (Why is that?)
• \(\Delta+300\) is a bound on the adjacent vertex distinguishing edge chromatic number
• Upper bounds for adjacent vertex-distinguishing edge coloring
• An improved upper bound on the adjacent vertex distinguishing total chromatic number of graphs
• Upper bounds on vertex distinguishing chromatic indices of some Halin graphs
• Asymptotically optimal bound on the adjacent vertex distinguishing edge choice number

This page was built for publication: An improved upper bound on the adjacent vertex distinguishing chromatic index of a graph

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