Neighbor-distinguishing indices of planar graphs with maximum degree ten

The neighbor-distinguishing index χa′(G) of a graph G is the smallest k for which G admits a proper edge k-coloring such that any two adjacent vertices have different color sets of their incident edges. It was conjectured that every simple graph G, different from a 5-cycle, without isolated edges ha...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2023-04, Vol.329, p.49-60
Main Authors: Huang, Danjun, Cai, Hongfeng, Wang, Weifan, Huo, Jingjing
Format: Article
Language:English
Subjects:
Discharging method
Maximum degree
Neighbor-distinguishing edge coloring
Planar graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The neighbor-distinguishing index χa′(G) of a graph G is the smallest k for which G admits a proper edge k-coloring such that any two adjacent vertices have different color sets of their incident edges. It was conjectured that every simple graph G, different from a 5-cycle, without isolated edges has χa′(G)≤Δ+2. In 2004, Horňák et al.confirmed the conjecture for planar graphs with Δ≥12. Recently, Cheng et al.extended this result to planar graphs with Δ≥11. In this paper, we furthermore improve the result to planar graphs with Δ≥10.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2022.12.023