List star edge-coloring of subcubic graphs

Samia Kerdjoudj, Alexandr Kostochka, André Raspaud

Research output: Contribution to journalArticlepeer-review

Abstract

A star edge-coloring of a graph G is a proper edge coloring such that every 2-colored connected subgraph of G is a path of length at most 3. For a graph G, let the list star chromatic index of G, chst(G), be the minimum k such that for any k-uniform list assignment L for the set of edges, G has a star edge-coloring from L. Dvořák, Mohar and Šámal asked whether the list star chromatic index of every subcubic graph is at most 7. We prove that it is at most 8. We also prove that if the maximum average degree of a subcubic graph G is less than 73 respectively, 25 , then chst(G) ≤ 5 (respectively, chst(G) ≤ 6).

Original languageEnglish (US)
Pages (from-to)1037-1054
Number of pages18
JournalDiscussiones Mathematicae - Graph Theory
Volume38
Issue number4
DOIs
StatePublished - 2018

Keywords

  • Edge coloring
  • Graph coloring
  • Planar graphs
  • Star coloring

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'List star edge-coloring of subcubic graphs'. Together they form a unique fingerprint.

Cite this