Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8900920 | Applied Mathematics and Computation | 2018 | 10 Pages |
Abstract
In this paper, we prove that if a graph G can be edge-partitioned into two graphs F and H, then Ïstâ²(G)â¤Ïstâ²(F)+Ïsâ²(H|G), where Ïsâ²(H|G) denotes the strong chromatic index of H restricted on G. Using this result, we give some upper bounds of the star chromatic index for planar graphs. Precisely, we show that (1) if G is a planar graph with maximum degree Î, then Ïstâ²(G)â¤2.75Î+18; (2) if G is a planar graph without 4-cycles, then Ïstâ²(G)â¤â1.5Îâ+18; (3) if G is a planar graph of girth at least 8, then Ïstâ²(G)â¤â1.5Îâ+3; (4) if G is a K4-minor free graph, then Ïstâ²(G)â¤2.25Î+6; and (5) if G is an outerplanar graph, then Ïstâ²(G)â¤â1.5Îâ+5, which improves a result in Bezegová et al. [2], which says that Ïstâ²(G)â¤â1.5Îâ+12 for an outerplanar graph G.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Yiqiao Wang, Weifan Wang, Ying Wang,