Strict neighbor-distinguishing index of K4-minor-free graphs
Strict neighbor-distinguishing index of K4-minor-free graphs
复制标题
DOI：
10.1016/j.dam.2023.01.017
复制
发表时间：
2023-04
影响因子：
1.1
通讯作者：
Jing Gu;Yiqiao Wang;Weifan Wang;Lina Zheng
中科院分区：
文献类型：
--
作者：
Jing Gu;Yiqiao Wang;Weifan Wang;Lina Zheng
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 with u and the set of colors used on the edges incident with v are not included in each other. The strict neighbor-distinguishing index χ snd′(G) of G is the minimum number of colors in a strict neighbor-distinguishing edge-coloring of G. A graph is formal if its minimum degree is at least 2. Let H n denote the graph obtained from the complete bipartite graph K 2, n by inserting a 2-vertex into one edge. In this paper, we prove that if G is a formal K 4-minor-free graph, then χ snd′(G)≤ 2 Δ+ 1, and moreover χ snd′(G)= 2 Δ+ 1 if and only if G is H Δ. This shows partially a conjecture, which says that every formal graph G, different from H Δ, has χ snd′(G)≤ 2 Δ.
