On the precise value of the strong chromatic-index of a planar graph with a large girth
Date Issued
2016
Date
2016
Author(s)
Duh, Guan-Huei
Abstract
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.
Subjects
Strong chromatic index
planar graph
girth
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-105-R03221028-1.pdf
Size
23.54 KB
Format
Adobe PDF
Checksum
(MD5):0cee1a704daa2a0acee2b703438bd767