The neighbor-distinguishing index <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\chi '_\textrm{a}(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>χ</mi> <mtext>a</mtext> <mo>′</mo> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> 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. A graph is called IC-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge and every vertex is incident with at most one crossing edge. It is known that every IC-planar graph G with maximum degree <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\Delta \ge 16$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo>≥</mo> <mn>16</mn> </mrow> </math></EquationSource> </InlineEquation> satisfies <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\chi '_\textrm{a}(G)\le \Delta +2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>χ</mi> <mtext>a</mtext> <mo>′</mo> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mi mathvariant="normal">Δ</mi> <mo>+</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. The condition <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\Delta \ge 16$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo>≥</mo> <mn>16</mn> </mrow> </math></EquationSource> </InlineEquation> is improved to <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\Delta \ge 14$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo>≥</mo> <mn>14</mn> </mrow> </math></EquationSource> </InlineEquation> in this paper.

Neighbor-distinguishing index of IC-planar graphs

期刊论文
发表日期：

2026年7月11日

查看全文

Zhengyue He,
Weifan Wang,
Lina Zheng

摘要

The neighbor-distinguishing index $\chi '_\textrm{a}(G)$ $χ_{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. A graph is called IC-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge and every vertex is incident with at most one crossing edge. It is known that every IC-planar graph G with maximum degree $\Delta \ge 16$ $Δ \geq 16$ satisfies $\chi '_\textrm{a}(G)\le \Delta +2$ $χ_{a}^{'} (G) \leq Δ + 2$ . The condition $\Delta \ge 16$ $Δ \geq 16$ is improved to $\Delta \ge 14$ $Δ \geq 14$ in this paper.