A star k-edge coloring is a proper edge coloring such that there are no bichromatic paths or cycles of length four. The smallest integer k such that G admits a star k-edge coloring is the star ...chromatic index of G. Deng et al. 5, and Bezegová et al. 1 independently proved that the star chromatic index of a tree is at most ⌊3Δ2⌋, and the bound is sharp. Han et al. 8 strengthened the result to list version of star chromatic index, and proved that ⌊3Δ2⌋ is also the sharp upper bound for the list star chromatic index of trees. A generalized Halin graph is a plane graph that consists of a plane embedding of a tree T with Δ(T)≥3, and a cycle C connecting all the leaves of the tree such that C is the boundary of the exterior face. In this paper, we prove that if H≔T∪C is a generalized Halin graph with |C|≠5, then its list star chromatic index is at mostmax{⌊θ(T)+Δ(T)2⌋,2⌊Δ(T)2⌋+7}, where θ(T)=maxxy∈E(T){dT(x)+dT(y)}. As a consequence, if H is a (generalized) Halin graph with maximum degree Δ≥13, then the list star chromatic index is at most ⌊3Δ2⌋. Moreover, the upper bound for the list star chromatic index is sharp.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPUK, ZAGLJ, ZRSKP
A star edge-coloring of a multigraph G is a proper edge-coloring of G such that no path or cycle of length four is bi-colored. The star chromatic index of G is the minimum number of colors needed to ...guarantee that G admits a star edge-coloring. The list star chromatic index of G is the smallest integer 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 proved that every subcubic multigraph has star chromatic index at most 7, and conjectured that 7 can be further improved to 6. Lužar, Mockovčiaková and Soták strengthened the result of Dvořák, Mohar and Šámal by showing that every subcubic multigraph has list star chromatic index at most 7. In this paper, we verify the conjecture of Dvořák, Mohar and Šámal for a class of subcubic multigraphs. We prove that every claw-free subcubic multigraph has list star chromatic index at most 6, and give a few examples to show that the upper bound is tight.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPUK, ZAGLJ, ZRSKP
A star edge‐coloring of a graph is a proper edge‐coloring without bichromatic paths and cycles of length four. In this paper, we consider the list version of this coloring and prove that the list ...star chromatic index of every subcubic graph is at most 7, answering the question of Dvořák et al (J Graph Theory, 72 (2013), 313‐326).
Full text
Available for:
BFBNIB, FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SAZU, SBCE, SBMB, UL, UM, UPUK
On a star chromatic index of subcubic graphs Lužar, Borut; Mockovčiaková, Martina; Soták, Roman
Electronic notes in discrete mathematics,
August 2017, 2017-08-00, Volume:
61
Journal Article
A star edge-coloring of a graph is a proper edge-coloring without bichromatic paths and cycles of length four. We consider the list version of this coloring and prove that the list star chromatic ...index of every subcubic graph is at most 7, answering the question of Dvořák et al. in Dvořák, Z., B. Mohar, and R. Šámal, Star chromatic index, J. Graph Theory 72 (2013), 313–326.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPUK, ZRSKP
Load filters
No result was selected!
Please select the results that you wish to export.
The search was successfully saved.
Editing
The search could not be saved.
Saved searches can be viewed in the list My searches.
The changes made to the saved search were saved successfully.
Save search
Shelf entry
No result was selected!
Adding material to shelf was successful.
Adding material to shelf was partly successful.
Adding material to shelf failed completely.
It was not necessary to add the material to the shelf.
Please select the results that you want to put on shelf!
On shelf the following records have been successfully added:
On shelf the following records have been successfully added:
PDF
