Publications
Sort:
Open Access Research Article Issue
Star edge coloring of K 2 , t -free planar graphs
AIMS Mathematics 2023, 8(6): 13154-13161
Published: 15 June 2023
Abstract PDF (262.5 KB) Collect
Downloads:2

The star chromatic index of a graph G, denoted by χ s t ( G ), is the smallest number of colors required to properly color E ( G ) such that every connected bicolored subgraph is a path with no more than three edges. A graph is K 2 , t -free if it contains no K 2 , t as a subgraph. This paper proves that every K 2 , t -free planar graph G satisfies χ s t ( G ) 1.5 Δ + 20 t + 20, which is sharp up to the constant term. In particular, our result provides a common generalization of previous results on star edge coloring of outerplanar graphs by Bezegová et al.(2016) and of C 4 -free planar graphs by Wang et al.(2018), as those graphs are subclasses of K 2 , 3 -free planar graphs.

Total 1