Star Chromatic Index Of Subcubic Multigraphs

Keywords

maximum average degree; star edge-coloring; subcubic multigraphs

Abstract

The star chromatic index of a multigraph G, denoted χ′s(G), is the minimum number of colors needed to properly color the edges of G such that no path or cycle of length four is bicolored. A multigraph G is star k-edge-colorable if χ′s(G)≤K. Dvořák, Mohar, and Šámal [Star chromatic index, J. Graph Theory 72 (2013), 313–326] proved that every subcubic multigraph is star 7-edge-colorable. They conjectured in the same article that every subcubic multigraph should be star 6-edge-colorable. In this article, we first prove that it is NP-complete to determine whether χ′s(G)≤3 for an arbitrary graph G. This answers a question of Mohar. We then establish some structure results on subcubic multigraphs G with ��δ(G) ≤ 2 such that χ′s(G)>K but χ′s(G-v)≤K for any v∈V(G),, where k∈{5,6}. We finally apply the structure results, along with a simple discharging method, to prove that every subcubic multigraph G is star 6-edge-colorable if mad(G)<5/2, and star 5-edge-colorable if mad(G)<24/11, respectively, where mad(G) is the maximum average degree of a multigraph G. This partially confirms the conjecture of Dvořák, Mohar, and Šámal.

Publication Date

8-1-2018

Publication Title

Journal of Graph Theory

Volume

88

Issue

4

Number of Pages

566-576

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1002/jgt.22230

Socpus ID

85045568328 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85045568328

This document is currently not available here.

Share

COinS