On star edge colorings of bipartite and subcubic graphs

Abstract: A star edge coloring of a graph is a proper edge coloring with no

2

-colored path or cycle of length four. The star chromatic index

c h i'_{s t} (G)

of

G

is the minimum number

t

for which

G

has a star edge coloring with

t

colors. We prove upper bounds for the star chromatic index of complete bipartite graphs; in particular we obtain tight upper bounds for the case when one part has size at most

3

. We also consider bipartite graphs

G

where all vertices in one part have maximum degree

2

and all vertices in the other part has maximum degree

b

. Let

k

be an integer (

k g e q 1

), we prove that if

b = 2 k + 1

then

c h i'_{s t} (G) l e q 3 k + 2

; and if

b = 2 k

, then

c h i'_{s t} (G) l e q 3 k

; both upper bounds are sharp. Finally, we consider the well-known conjecture that subcubic graphs have star chromatic index at most

6

; in particular we settle this conjecture for cubic Halin graphs.

Review text

A star edge coloring of a graph is a proper edge coloring with no \(2\)-colored path or cycle of length four. The star chromatic index \(ch^\prime_{st}(G)\) of a graph \(G\) is the minimum number \(t\) for which \(G\) has a star edge coloring with \(t\) colors. Star edge colorings of graphs were introduced by \textit{X. Liu} and \textit{K. Deng} [J. Lanzhou Univ., Nat. Sci. 44, No. 2, 98--99, 102 (2008; Zbl 1174.05369)] motivated by the vertex colouring version. Later in [J. Graph Theory 72, No. 3--4, 313--326 (2013; Zbl 1262.05049)], \textit{Z. Dvořák} et al. studied star edge colorings of complete graphs, obtaining upper and lower bounds for the star chromatic index of such graphs. Other results has been obtained for star edge colorings of trees and outerplanar graphs [\textit{L. Bezegová} et al., ibid. 81, No. 1, 73--82 (2016; Zbl 1330.05059)], for graphs with maximum degree four [\textit{Y. Wang} et al., Appl. Math. Comput. 340, 268--275 (2019; Zbl 1428.05121)], and for planar graphs [\textit{Y. Wang} et al., ibid. 333, 480--489 (2018; Zbl 1427.05092)]. In the literature, there exist results also on star edge colorings of subcubic and sparse graphs. In the first part of the paper, the authors consider star edge colorings of bipartite graphs. They obtain the star chromatic index of complete bipartite graphs in the case that one part has size at most three and they provide some bounds in the other cases for complete bipartite graphs. Moreover, they provide upper bounds for the star chromatic index of bipartite graphs where the vertices in one part have small degree and a sharp upper bound in the case that one part has maximum degree two. In the second part of the paper, the authors verify a conjecture given by \textit{Z. Dvořák} et al. [J. Graph Theory 72, No. 3--4, 313--326 (2013; Zbl 1262.05049)] stating that a graph with maximum degree at 3 has star chromatic index at most 6, in the case that \(G\) is a bipartite graph with one part of maximum degree 2, a cubic Halin graph and another family of planar graphs.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: On star edge colorings of bipartite and subcubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2028078)