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.
Citation: Yunfeng Tang, Huixin Yin, Miaomiao Han. Star edge coloring of $ K_{2, t} $-free planar graphs[J]. AIMS Mathematics, 2023, 8(6): 13154-13161. doi: 10.3934/math.2023664
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.
| [1] |
V. G. Vizing, On an estimate of the chromatic index of a $p$-graph, Diskret. Anal., 3 (1964), 25–30. http://dx.doi.org/10.1090/S0894-0347-1992-1124979-1 doi: 10.1090/S0894-0347-1992-1124979-1
|
| [2] |
J. L. Fouquet, J. L. Jolivet, Strong edge-colorings of graphs and applicantions to multi-k-gons, Ars Comb., 16 (A) (1983), 141–150. http://dx.doi.org/10.1090/S0894-0347-1992-1124979-1 doi: 10.1090/S0894-0347-1992-1124979-1
|
| [3] |
X. S. Liu, K. Deng, An upper bound on the star chromatic index of graphs with $\Delta\ge 7$, J. Lanzhou Univ. (Nat. Sci.), 2 (2008), 98–99. http://dx.doi.org/10.1090/S0894-0347-1992-1124979-1 doi: 10.1090/S0894-0347-1992-1124979-1
|
| [4] |
H. Lei, Y. Shi, Z. Song, Star chromatic index of subcubic multigraph, J. Graph Theory, 88 (2018), 566–576. https://doi.org/10.1002/jgt.22230 doi: 10.1002/jgt.22230
|
| [5] |
Z. Dvořák, B. Mohar, R. Šámal, Star chromatic index, J. Graph Theory, 72 (2013), 313–326. https://doi.org/10.1002/jgt.21644 doi: 10.1002/jgt.21644
|
| [6] |
K. Deng, X. S. Liu, S. L. Tian, Star edge coloring of trees, (in Chinese) J. Shandong Univ. Nat. Sci., 46 (2011), 84–88. http://dx.doi.org/10.1090/S0894-0347-1992-1124979-1 doi: 10.1090/S0894-0347-1992-1124979-1
|
| [7] |
L'. Bezegová, B. Lužar, M. Mocko$\mathop {\rm{v}}\limits^ \vee $ciaková, R. Soták, R. Škrekovski, Star edge coloring of some classes of graphs, J. Graph Theory, 81 (2016), 73–82. https://doi.org/10.1002/jgt.21862 doi: 10.1002/jgt.21862
|
| [8] |
Y. Wang, W. Wang, Y. Wang, Edge-partition and star chromatic index, Appl. Math. Comput., 333 (2018), 480–489. https://doi.org/10.1016/j.amc.2018.03.079 doi: 10.1016/j.amc.2018.03.079
|
| [9] |
J. Li, K. Horacek, R. Luo, Z. Miao, Upper Bounds on List Star Chromatic Index of Sparse Graphs, Acta Math. Sin. (Engl. Ser.), 36 (2020), 1–12. https://doi.org/10.1007/s10114-019-8546-7 doi: 10.1007/s10114-019-8546-7
|
| [10] |
D. P. Sanders, Y. Zhao, Planar graphs of maximum degree seven are class 1, J. Combin. Theory Ser. B, 83 (2001), 202–212. https://doi.org/10.1006/jctb.2001.2047 doi: 10.1006/jctb.2001.2047
|
| [11] |
L. Zhang, Every planar graph with maximum degree 7 is of class 1, Graphs Combin., 16 (2000), 457–495. http://doi.org/10.1007/s003730070009 doi: 10.1007/s003730070009
|
Figures(1)
Yunfeng Tang, Huixin Yin, Miaomiao Han. Star edge coloring of $ K_{2, t} $-free planar graphs[J]. AIMS Mathematics, 2023, 8(6): 13154-13161. doi: 10.3934/math.2023664
DownLoad: