Strict neighbor-distinguishing index of planar graphs without 4-cycles

Abstract

A proper edge coloring of a graph G is strict neighbor-distinguishing if for any two adjacent vertices u and v, the set of colors used on the edges incident to u and the set of colors used on the edges incident to v are not included with each other. The strict neighbor-distinguishing index of G is the minimum number χsnd′(G) of colors in a strict neighbor-distinguishing edge coloring of G. It was conjectured that every simple graph G without leaves has χsnd′(G) ⩽ 2Δ except a special graph HΔ. We show that if G is a planar graph without 4-cycles, then χsnd′(G) ⩽ Δ + 300.