Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs

Abstract

We prove that every planar graph with maximum degree ∆ is strong edge (2∆−1)-colorable if its girth is at least 40+1. The bound 2∆−1 is reached at any graph that has two adjacent vertices of degree ∆.

Keywords

• planar graph
• edge coloring
• 2-distance coloring
• strong edgecoloring