Edge-partition and star chromatic index

摘要

The star chromatic index χst′(G) of a graph G is the smallest integer k for which G has a proper edge k-coloring without bichromatic paths or cycles of length four. The strong chromatic index χs′(G) of G is the smallest integer k for which G has a proper edge k-coloring such that any two edges at distance at most two get distinct colors.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.