Strong edge-coloring for planar graphs with large girth

Document Type

Article

Publication Date

2-1-2019

Abstract

A strong edge-coloring of a graph [Formula presented] is a partition of its edge set [Formula presented] into induced matchings. Let [Formula presented] be a connected planar graph with girth [Formula presented] and maximum degree [Formula presented]. We show that either [Formula presented] is isomorphic to a subgraph of a very special [Formula presented]-regular graph with girth [Formula presented], or [Formula presented] has a strong edge-coloring using at most [Formula presented] colors.

DOI

10.1016/j.disc.2018.10.019

Find in your library

Off-Campus WSU Users


Share

COinS