List Star Edge-Coloring of Subcubic Graphs
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 s...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2018-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2037 |
| _version_ | 1797718030433648640 |
|---|---|
| author | Kerdjoudj Samia Kostochka Alexandr Raspaud André |
| author_facet | Kerdjoudj Samia Kostochka Alexandr Raspaud André |
| author_sort | Kerdjoudj Samia |
| collection | DOAJ |
| description | 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. 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${7 \over 3}$ (respectively, 52${5 \over 2}$), then ch′st(G) ≤ 5 (respectively, ch′st(G) ≤ 6). |
| first_indexed | 2024-03-12T08:45:02Z |
| format | Article |
| id | doaj.art-9dc4c773c085491fb23aa369284fe45c |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:45:02Z |
| publishDate | 2018-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-9dc4c773c085491fb23aa369284fe45c2023-09-02T16:29:57ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922018-11-013841037105410.7151/dmgt.2037dmgt.2037List Star Edge-Coloring of Subcubic GraphsKerdjoudj Samia0Kostochka Alexandr1Raspaud André2L’IFORCE, Faculty of Mathematics, USTHB, BP 32 El-Alia, Bab-Ezzouar 16111, Algiers, AlgeriaUniversity of Illinois at Urbana-Champaign, Urbana, IL 61801, USA and Sobolev Institute of MathematicsNovosibirsk630090, RussiaLaBRI (Université de Bordeaux), 351 cours de la Libération 33405Talence Cedex, FranceA 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. 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${7 \over 3}$ (respectively, 52${5 \over 2}$), then ch′st(G) ≤ 5 (respectively, ch′st(G) ≤ 6).https://doi.org/10.7151/dmgt.2037graph coloringedge coloringstar coloringplanar graphs05c15 |
| spellingShingle | Kerdjoudj Samia Kostochka Alexandr Raspaud André List Star Edge-Coloring of Subcubic Graphs Discussiones Mathematicae Graph Theory graph coloring edge coloring star coloring planar graphs 05c15 |
| title | List Star Edge-Coloring of Subcubic Graphs |
| title_full | List Star Edge-Coloring of Subcubic Graphs |
| title_fullStr | List Star Edge-Coloring of Subcubic Graphs |
| title_full_unstemmed | List Star Edge-Coloring of Subcubic Graphs |
| title_short | List Star Edge-Coloring of Subcubic Graphs |
| title_sort | list star edge coloring of subcubic graphs |
| topic | graph coloring edge coloring star coloring planar graphs 05c15 |
| url | https://doi.org/10.7151/dmgt.2037 |
| work_keys_str_mv | AT kerdjoudjsamia liststaredgecoloringofsubcubicgraphs AT kostochkaalexandr liststaredgecoloringofsubcubicgraphs AT raspaudandre liststaredgecoloringofsubcubicgraphs |