Star 5-Edge-Colorings Of Subcubic Multigraphs

Keywords

Maximum average degree; Star edge-coloring; Subcubic multigraphs

Abstract

The star chromatic index of a mulitigraph 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 bi-colored. A multigraph G is star k-edge-colorable if χs′(G)≤k. Dvořák et al. (2013) proved that every subcubic multigraph is star 7-edge-colorable, and conjectured that every subcubic multigraph should be star 6-edge-colorable. Kerdjoudj, Kostochka and Raspaud considered the list version of this problem for simple graphs and proved that every subcubic graph with maximum average degree less than 7∕3 is star list-5-edge-colorable. It is known that a graph with maximum average degree 14∕5 is not necessarily star 5-edge-colorable. In this paper, we prove that every subcubic multigraph with maximum average degree less than 12∕5 is star 5-edge-colorable.

Publication Date

4-1-2018

Publication Title

Discrete Mathematics

Volume

341

Issue

4

Number of Pages

950-956

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.disc.2017.12.008

Socpus ID

85041673850 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS