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

preprint2015arXivOpen access

Abstract

A strong kk-edge-coloring of a graph GG is a mapping from E(G)E(G) to {1,2,…,k}\{1,2,\ldots,k\} such that every pair of distinct edges at distance at most two receive different colors. The strong chromatic index χs′(G)χ'_s(G) of a graph GG is the minimum kk for which GG has a strong kk-edge-coloring. Denote σ(G)=max⁡xy∈E(G){deg⁡(x)+deg⁡(y)−1}σ(G)=\max_{xy\in E(G)}\{\operatorname{deg}(x)+\operatorname{deg}(y)-1\}. It is easy to see that σ(G)≤χs′(G)σ(G) \le χ'_s(G) for any graph GG, and the equality holds when GG is a tree. For a planar graph GG of maximum degree ΔΔ, it was proved that χs′(G)≤4Δ+4χ'_s(G) \le 4 Δ+4 by using the Four Color Theorem. The upper bound was then reduced to 4Δ4Δ, 3Δ+53Δ+5, 3Δ+13Δ+1, 3Δ3Δ, 2Δ−12Δ-1 under different conditions for ΔΔ and the girth. In this paper, we prove that if the girth of a planar graph GG is large enough and σ(G)≥Δ(G)+2σ(G)\geq Δ(G)+2, then the strong chromatic index of GG is precisely σ(G)σ(G). This result reflects the intuition that a planar graph with a large girth locally looks like a tree.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.