2018•Discussiones Mathematicae Graph TheoryOpen access

List star edge-coloring of subcubic graphs

Samia Kerdjoudj, Alexander V. Kostochka, André Raspaud

Open full text 17 citations

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, ch st (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. Dvok, 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 7 3 respectively, 5 2 , then ch st (G) 5 (respectively, ch st (G) 6).

Open-access reader

About this research paper

What this paper is about

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, ch st (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. Dvok, 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 7 3 respectively, 5 2 , then ch st (G) 5 (respectively, ch st (G) 6).

Why it matters

OpenAlex reports 17 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available 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, ch st (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. Dvok, 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 7 3 respectively, 5 2 , then ch st (G) 5 (respectively, ch st (G) 6).

Key concepts: Mathematics, Combinatorics, Edge coloring, Star (game theory), Graph, List coloring, Chromatic scale, Discrete mathematics

Related papers

Back to paper searchBrowse research topicsOriginal source
List star edge-coloring of subcubic graphs — Research Paper | ScholarLens