Star edge coloring of $ K_{2, t} $-free planar graphs
Authors:
Open Access
- 1 January 2023
- journal article
- research article
- Published by American Institute of Mathematical Sciences (AIMS) in AIMS Mathematics
- Vol. 8 (6) , 13154-13161
Abstract
The star chromatic index of a graph $ G $, denoted by $ \chi{'}_{st}(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 $ \chi_{st}'(G)\le 1.5\Delta +20t+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.
Keywords
This publication has 8 references indexed in Scilit:
- Upper Bounds on List Star Chromatic Index of Sparse GraphsActa Mathematica Sinica, English Series, 2019
- Edge-partition and star chromatic indexApplied Mathematics and Computation, 2018
- Star chromatic index of subcubic multigraphsJournal of Graph Theory, 2017
- Star Edge Coloring of Some Classes of GraphsJournal of Graph Theory, 2015
- Star Chromatic IndexJournal of Graph Theory, 2012
- Planar Graphs of Maximum Degree Seven are Class IJournal of Combinatorial Theory, Series B, 2001
- Every Planar Graph with Maximum Degree 7 Is of Class 1Graphs and Combinatorics, 2000
- Flots d’Anosov à distributions stable et instable différentiablesJournal of the American Mathematical Society, 1992