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

DOI10.1016/J.DAM.2013.08.038MaRDI QIDQ741759zbMATH OpenOpenAlexFDO

Authors Ko-Wei Lih, Lianzhu Zhang, Weifan Wang

Publication date 12 September 2014

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

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

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)

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.

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

Cites work

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

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
• scientific article; zbMATH DE number 7108817 (Why is no real title available?)
• scientific article; zbMATH DE number 5732458 (Why is no real title available?)
• Adjacent Vertex Distinguishing Edge‐Colorings
• 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
• Edge-partitions of graphs and their neighbor-distinguishing index
• On the inclusion chromatic index of a Halin graph
• 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
• \(\Delta+300\) is a bound on the adjacent vertex distinguishing edge chromatic number
• scientific article; zbMATH DE number 6769480 (Why is no real title available?)
• 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)