×

List star chromatic index of sparse graphs. (English) Zbl 1387.05090

Summary: 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\), \(\operatorname{ch}_s^\prime(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\). Z. Dvořák et al. [J. Graph Theory 72, No. 3–4, 313–326 (2013; Zbl 1262.05049)] asked whether the list star chromatic index of every subcubic graph is at most 7. In [Discrete Math. 341, No. 7, 1835–1849 (2018; Zbl 1387.05090)] the authors proved that it is at most 8. In this paper we consider graphs with any maximum degree, we proved that if the maximum average degree of a graph \(G\) is less than \(\frac{14}{5}\) (resp. 3), then \(\operatorname{ch}_s^\prime(G) \leq 2 \varDelta(G) + 2\) (resp. \(\operatorname{ch}_s^\prime(G) \leq 2 \varDelta(G) + 3\)).

MSC:

05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bezegova, L.; Lužar, B.; Mockovčiaková, M.; Soták, R.; Škrekovski, R., Star edge coloring of some classes of graphs, J. Graph Theory, 81, 1, 73-82 (2016) · Zbl 1330.05059
[2] Choi, I.; Kim, J.; Kostochka, A. V.; Raspaud, A., Strong edge-colorings of sparse graphs with large maximum degree, European J. Combin., 67, 21-39 (2018) · Zbl 1371.05076
[3] Deng, K.; Liu, X. S.; Tian, S. L., Star edge coloring of trees, J. Shandong Univ. Nat. Sci., 46, 8, 84-88 (2011), (in Chinese)
[4] Dvořák, Z.; Mohar, B.; Šámal, R., Star chromatic index, J. Graph Theory, 72, 313-326 (2013) · Zbl 1262.05049
[5] Faudree, R. J.; Gyàrfas, A.; Schelp, R. H.; Tuza, Zs., The strong chromatic index of graphs, Ars Combin., 29, 205-211 (1990) · Zbl 0721.05018
[6] Fertin, G.; Raspaud, A.; Reed, B., (On Star Coloring of Graphs. On Star Coloring of Graphs, Lecture Notes in Comput. Sci., vol. 2204 (2001), Springer: Springer Berlin), 140-153 · Zbl 1042.68628
[7] Grünbaum, B., Acyclic colorings of planar graphs, Israel J. Math., 14, 390-408 (1973) · Zbl 0265.05103
[8] Kerdjoudj, S.; Kostochka, A. V.; Raspaud, A., List star edge coloring of subcubic graphs, Discuss. Math. Graph Theory (2017), in press · Zbl 1392.05040
[9] Kerdjoudj, S.; Raspaud, A., List star edge coloring of sparse graphs, Discrete Appl. Math., 238, 115-125 (2018) · Zbl 1380.05070
[10] Lei, H.; Shi, Y.; Song, Z.-X., Star chromatic index of subcubic multigraphs, J. Graph Theory (2018), in press · Zbl 1393.05119
[11] Liu, X. S.; Deng, K., An upper bound on the star chromatic index of graphs with \(\delta \leq 7\), J. Lanzhou Univ. (Nat. Sci.), 44, 94-95 (2008)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.