大腰圍平面圖的強邊著色數之精確值

Abstract

一個圖 $G$ 的 $k$-強邊著色指的是使得距離為二以內的邊都塗不同顏色的 $k$-邊著色；強邊著色數 $chi'_s(G)$ 則標明參數 $k$ 的最小可能。此概念最初是為了解決平地上設置廣播網路的問題，由 Fouquet 與 Jolivet 提出。對於任意圖 $G$，參數 $sigma(G)=max_{xyin E(G)}{deg(x)+deg(y)-1}$是強邊著色數的一個下界；且若 $G$ 是樹，則強邊著色數會到達此下界。另一方面，對於最大度數為 $Delta$ 的平面圖$G$，經由四色定理可以證得 $chi'_s(G)leq 4Delta+4$。更進一步，在各種腰圍與最大度數的條件下，平面圖的強邊著色數之上界分別有$4Delta$, $3Delta+5$, $3Delta+1$, $3Delta$ 和 $2Delta-1$ 等等優化。本篇論文說明當平面圖 $G$ 的腰圍夠大，且$sigma(G)geqDelta(G)+2$ 時，參數 $sigma(G)$ 就會恰好是此圖的強邊著色數。本結果反映出大腰圍的平面圖局部上有看似樹的結構。

A {em strong $k$-edge-coloring} of a graph $G$ is a mapping from the edge set $E(G)$ to ${1,2,ldots,k}$ such that every pair of distinct edges at distance at most two receive different colors. The {it strong chromatic index} $chi'_s(G)$ of a graph $G$ is the minimum $k$ for which $G$ has a strong $k$-edge-coloring. The concept of strong edge-coloring was introduced by Fouquet and Jolivet to model the channel assignment in some radio networks. Denote the parameter $sigma(G)=max_{xyin E(G)}{deg(x)+deg(y)-1}$. It is easy to see that $sigma(G) le chi'_s(G)$ for any graph $G$, and the equality holds when $G$ is a tree. For a planar graph $G$ of maximum degree $Delta$, it was proved that $chi'_s(G) le 4 Delta +4$ by using the Four Color Theorem. The upper bound was then reduced to $4Delta$, $3Delta+5$, $3Delta+1$, $3Delta$, $2Delta-1$ under different conditions for $Delta$ and the girth. In this paper, we prove that if the girth of a planar graph $G$ is large enough and $sigma(G)geq Delta(G)+2$, then the strong chromatic index of $G$ is precisely $sigma(G)$. This result reflects the intuition that a planar graph with a large girth locally looks like a tree.