On the precise value of the strong chromatic index of a planar graph with a large girth

摘要

Astrongk-edge-coloringof a graphGis a mapping fromE(G)to{1,2,…,k}such that every pair of distinct edges at distance at most two receive different colors. Thestrong chromatic indexχs′(G)of a graphGis the minimumkfor whichGhas a strongk-edge-coloring. Denoteσ(G)=maxxy∈E(G){deg(x)+deg(y)?1}. It is easy to see thatσ(G)≤χs′(G)for any graphG, and the equality holds whenGis a tree. For a planar graphGof maximum degreeΔ, it was proved thatχs′(G)≤4Δ+4by using the Four Color Theorem. The upper bound was then reduced to4Δ,3Δ+5,3Δ+1,3Δ,2Δ?1under different conditions forΔand the girth. In this paper, we prove that if the girth of a planar graphGis large enough andσ(G)≥Δ(G)+2, then the strong chromatic index ofGis preciselyσ(G). This result reflects the intuition that a planar graph with a large girth locally looks like a tree.