A survey on star edge-coloring of graphs

All multigraphs in this paper are finite and loopless; and all graphs are finite and without loops or multiple edges. Given a multigraph $G$, let $c:E(G)\rightarrow[k]$ be a proper edge-coloring of $G$, where $k\geq 1$ is an integer and $[k]:=\{1,2,\dots,k\}$. We say that $c$ is a star $k$-edge-coloring of $G$ if no path or cycle of length four in $G$ is bicolored under the coloring $c$; and $G$ is star $k$-edge-colorable if $G$ admits a star $k$-edge-coloring. The star chromatic index of $G$, denoted $\chi^{\prime}_{st}(G)$, is the smallest integer $k$ such that $G$ is star $k$-edge-colorable. The chromatic index and chromatic number of $G$ are denoted by $\chi^{\prime}(G)$ and $\chi(G)$. As pointed out in [9], the definition of star edge-coloring of a graph $G$ is equivalent to the star vertex-coloring of its line graph $L(G)$. Star edge-coloring of a graph was initiated by Liu and Deng [29], motivated by the vertex version (see [1, 4, 5, 8, 24, 35]). Given a multigraph $G$, we use $|G|$ to denote the number of vertices, $e(G)$ the number of edges, $\delta(G)$ the minimum degree, and $\Delta(G)$ the maximum degree of $G$, respectively. We use $K_{n}$, $P_{n}$ and $C_{n}$ to denote the complete graph, the path and the cycle on $n$ vertices, respectively. The maximum average degree of a multigraph $G$, denoted $\text{mad}(G)$, is defined as the maximum of $2e(H)/|H|$ taken over all the non-empty subgraphs $H$ of $G$. The girth of a graph with a cycle is the length of its shortest cycle. A graph with no cycle has infinite girth. The following first upper bound is a result of Liu and Deng [29].

Theorem 1.2 below is a result of Dvořák, Mohar, and Šámal [9], which give an upper and a lower bounds for complete graphs.

They proved the upper bound using a nontrivial result about sets without arithmetic progressions, and up till now, it is still the best known. For the lower bound, they used an elegant double counting approach. The authors of [2] observed a improvement in their proof and obtained the bound $\chi^{\prime}_{st}(K_{n})\geq 3n(n-1)/(n+4)$ (see [33] for a proof).

Currently the best upper bound in terms of the maximum degree for general graphs is also derived in [9] using Theorem 1.2.

The true order of magnitude of $\chi^{\prime}_{st}(K_{n})$ is still unknown. Dvořák, Mohar, and Šámal [9] made the following question.

Dvořák, Mohar, and Šámal [9] also mentioned that, if convenient, one may start with other special graphs in place of $K_{n}$, in particular, from Observation 1.5 it follows that if $\chi^{\prime}_{st}(K_{n,n})$ is $O(n)$(or $n(\log n)^{O(1)}$, $n^{1+o(1)}$, respectively), then $\chi^{\prime}_{st}(K_{n})$ is $O(n\log n)$(or $n(\log n)^{O(1)}$, $n^{1+o(1)}$, respectively).

The paper is organized as follows. The first Section 2 contains the results on algorithmic aspects of the star edge-coloring. In Sections 3, 4, 5 we present the results of star chromatic index on subcubic graphs, bipartite graphs, and planar graphs, respectively. Star edge-coloring is naturally generalized to the list version and it was pointed out in [9]: It would be interesting to understand the list version of star edge-coloring. The results of list star edge-coloring are presented in Section 6. Finally in Section 7 we summarize the results of the star chromatic index of another family of graphs such as Halin graphs, generalized Petersen graphs, products of graphs and so on.

It is well-known [39] that the chromatic index of a graph with maximum degree $\Delta$ is either $\Delta$ or $\Delta+1$. However, it is NP-complete [18] to determine whether the chromatic index of an arbitrary graph with maximum degree $\Delta$ is $\Delta$ or $\Delta+1$. The problem remains NP-complete even for cubic graphs (the degree of all vertices is 3). Lei, Shi, and Song [27] proved the following result.

Given a cubic graph $G$, is $G$ $3$-edge-colorable?

Clearly, SEC is in the class NP. We shall reduce 3EC to SEC.

Let $H$ be an instance of 3EC. We construct a graph $G$ from $H$ by replacing each edge $e=uw\in E(H)$ with a copy of graph $H_{ab}$, identifying $u$ with $a$ and $w$ with $b$, where $H_{ab}$ is depicted in Figure 1. The size of $G$ is clearly polynomial in the size of $H$, and $\Delta(G)=3$.

It suffices to show that $\chi^{\prime}(H)\leq 3$ if and only if $\chi^{\prime}_{st}(G)\leq 3$. Assume that $\chi^{\prime}(H)\leq 3$. Let $c:E(H)\rightarrow\{1,2,3\}$ be a proper $3$-edge-coloring of $H$. Let $c^{*}$ be an edge coloring of $G$ obtained from $c$ as follows: for each edge $e=uw\in E(H)$, let $c^{*}(av^{e}_{1})=c^{*}(v^{e}_{3}v^{e}_{4})=c^{*}(v^{e}_{6}b)=c(uw)$, $c^{*}(v^{e}_{1}v^{e}_{2})=c^{*}(v^{e}_{3}v^{e}_{7})=c^{*}(v^{e}_{4}v^{e}_{8})=c^{*}(v^{e}_{5}v^{e}_{6})=c(uw)+1$, and $c^{*}(v^{e}_{2}v^{e}_{3})=c^{*}(v^{e}_{4}v^{e}_{5})=c(uw)+2$, where all colors here and henceforth are done modulo $3$. Notice that $c^{*}$ is a proper $3$-edge-coloring of $G$. Furthermore, it can be easily checked that $G$ has no bicolored path or cycle of length four under the coloring $c^{*}$. Thus $c^{*}$ is a star $3$-edge-coloring of $G$ and so $\chi^{\prime}_{st}(G)\leq 3$.

Conversely, assume that $\chi^{\prime}_{st}(G)\leq 3$. Let $c^{*}:E(G)\rightarrow\{1,2,3\}$ be a star $3$-edge-coloring of $G$. Let $c$ be an edge-coloring of $H$ obtained from $c^{*}$ by letting $c(e)=c^{*}(av^{e}_{1})$ for any $e=uw\in E(H)$. Clearly, $c$ is a proper $3$-edge-coloring of $H$ if for any edge $e=uw$ in $G$, $c^{*}(av^{e}_{1})=c^{*}(v^{e}_{6}b)$. We prove this next. Let $e=uw$ be an edge of $H$. We consider the following two cases.

In this case, let $c^{*}(v^{e}_{3}v^{e}_{7})=c^{*}(v^{e}_{4}v^{e}_{8})=\alpha$, where $\alpha\in\{1,2,3\}$. We may further assume that $c^{*}(v^{e}_{3}v^{e}_{4})=\beta$ and $c^{*}(v^{e}_{2}v^{e}_{3})=c^{*}(v^{e}_{4}v^{e}_{5})=\gamma$, where $\{\beta,\gamma\}=\{1,2,3\}\backslash\alpha$. This is possible because $d_{G}(v^{e}_{3})=d_{G}(v^{e}_{4})=3$ and $c^{*}$ is a proper $3$-edge-coloring of $G$. Since $c^{*}$ is a star edge-coloring of $G$, we see that $c^{*}(v^{e}_{1}v^{e}_{2})=c^{*}(v^{e}_{5}v^{e}_{6})=\alpha$ and so $c^{*}(av^{e}_{1})=c^{*}(v^{e}_{6}b)=\beta$.

In this case, let $c^{*}(v^{e}_{3}v^{e}_{7})=\alpha$, $c^{*}(v^{e}_{4}v^{e}_{8})=\beta$, $c^{*}(v^{e}_{3}v^{e}_{4})=\gamma$, where $\{\alpha,\beta,\gamma\}=\{1,2,3\}$. This is possible because $\alpha\neq\beta$ by assumption. Since $c^{*}$ is a proper edge-coloring of $G$, we see that $c^{*}(v^{e}_{2}v^{e}_{3})=\beta$ and $c^{*}(v^{e}_{4}v^{e}_{5})=\alpha$. One can easily check now that $c^{*}(v^{e}_{1}v^{e}_{2})=\alpha$ and $c^{*}(v^{e}_{5}v^{e}_{6})=\beta$, and so $c^{*}(av^{e}_{1})=c^{*}(v^{e}_{6}b)=\gamma$, because $c^{*}$ is a star edge-coloring of $G$.

In both cases we see that $c^{*}(av^{e}_{1})=c^{*}(v^{e}_{6}b)$. Therefore $c$ is a proper $3$-edge-coloring of $H$ and so $\chi^{\prime}(H)\leq 3$. This completes the proof of Theorem 2.1.  

There are few results for the computational complexity of the star edge-coloring problem. In [36], Omoomi, Roshanbin, and Dastjerdi presented a polynomial time algorithm that finds an optimum star edge-coloring for every tree.

A multigraph $G$ is subcubic if all its vertices have degree less than or equal to three. Dvořák, Mohar, and Šámal [9] considered the star chromatic index of subcubic multigraphs. To state their result, we need to introduce one notation. A graph $G$ covers a graph $H$ if there is a mapping $f:V(G)\rightarrow V(H)$ such that for any $uv\in E(G)$, $f(u)f(v)\in E(H)$, and for any $u\in V(G)$, $f$ is a bijection between $N_{G}(u)$ and $N_{H}(f(u))$. They proved the following.

As observed in [9], $K_{3,3}$ and the Heawood graph are star $6$-edge-colorable. No subcubic multigraphs with star chromatic index seven are known. Dvořák, Mohar, and Šámal [9] proposed the following conjecture.

It was shown that every subcubic outerplanar graph is star $5$-edge-colorable in [2] and every cubic Halin graph is star $6$-edge-colorable in [6, 19]. Lei, Shi, and Song [27] proved that

Later, Lei, Shi, Song, and Wang [28] improved Theorem 3.3(b) by showing the following result.

We don’t know if the bound $12/5$ in Theorem 3.4 is best possible. The graph depicted in Figure 2 has maximum average degree $14/5$ but is not star $5$-edge-colorable.

In [43], Wang, Wang, and Wang focused on the star edge-coloring of graphs with maximum degree four and proved the following result.

In this section we consider the star edge-coloring of bipartite graphs. We first consider complete bipartite graphs. Let $K_{m,n}$ denote the complete bipartite graph in which the orders of its bipartition sets are $m$ and $n$, where $m\leq n$. Trivially $\chi^{\prime}_{st}(K_{1,n})=n$.

Dvorak, Mohar, and Šámal [9] obtained Observation 4.1, thus proved an asymptotically bound on $\chi^{\prime}_{st}(K_{n,n})$: it follows from Theorem 1.2 that for every $\varepsilon>0$, there is a constant $C>0$, such that for every $n\geq 1$, $\chi^{\prime}_{st}(K_{n,n})\leq Cn^{1+\varepsilon}$.

Wang, Wang, and Wang [43] proved that $\chi^{\prime}_{st}(K_{3,4})=7$, and it is known that $\chi^{\prime}_{st}(K_{3,3})=6$ in [9]. Casselgren, Granholm, and Raspaud [6] obtained the following results.

Some exact values of $\chi^{\prime}_{st}(K_{m,n})$ are given by Casselgren, Granholm, and Raspaud [6] in the following Table 1.

Moreover, using the idea in the proof of Theorem 4.2(c), one can prove lower bounds on the star chromatic index for further families of complete bipartite graphs. Let us here just list a few cases corresponding to the values in the Table 1(see [6]).

• •

  $\chi^{\prime}_{st}(K_{5,n})\geq\frac{5n}{3}$.

• •

  $\chi^{\prime}_{st}(K_{6,n})\geq\frac{7n}{4}$.

• •

  $\chi^{\prime}_{st}(K_{7,n})\geq\frac{7n}{4}$.

• •

  $\chi^{\prime}_{st}(K_{8,n})\geq\frac{9n}{5}$.

Next, we turn to general bipartite graphs with restrictions on the vertex degrees. In the following we use the notation $G=(X,Y;E)$ for a bipartite graph $G$ with parts $X$ and $Y$ and edge set $E=E(G)$. We denote by $\Delta(X)$ and $\Delta(Y)$ the maximum degrees of the vertices in the parts $X$ and $Y$, respectively. A bipartite graph $G=(X,Y;E)$ where all vertices in $X$ have degree $r$ and all vertices in $Y$ have degree $d$ is called $(r,d)$-biregular.

If the vertices in one part of a bipartite graph $G$ have maximum degree 1, then trivially $\chi^{\prime}_{st}(G)=\Delta(G)$. For the case when the vertices in one of the parts have maximum degree two, Casselgren, Granholm, and Raspaud [6] proved the following.

Note that the upper bounds in Theorem 4.3 are sharp. This can be obtained from Theorem 4.2(a).

By Theorem 4.3, one can get the following corollary for $(2,d)$-biregular graphs.

Melinder [32] gave a general upper bound on the star chromatic index of biregular graphs.

Now we consider the star chromatic index of bipartite graphs in terms of the maximum degree. By Theorem 3.1, we have $\chi^{\prime}_{st}(G)\leq 7$ if $G$ is a bipartite graph with $\Delta(G)=3$. Wang, Wang, and Wang [43] considered bipartite graphs with $\Delta(G)=4$ and proved the following.

Since $K_{4,4}$ requires 7 colours, and no graph requiring 8 colours has been found, the smallest upper bound is at least 7 [6].

Recently, Melinder [32] gave a general upper bound for bipartite graphs with maximum degree.

Melinder [32] also proved an upper bound for a special case of multipartite graphs.

Deng, Liu, and Tian [11] and Bezegová, Lužar, Mockovčiaková, Soták, and Škrekovski [2] independently proved that for each tree $T$ with maximum degree $\Delta$, its star chromatic index $\chi^{\prime}_{st}(T)\leq\left\lfloor\frac{3\Delta}{2}\right\rfloor$, Moreover, the bound is tight. Bezegová, Lužar, Mockovčiaková, Soták, and Škrekovski [2] investigated the star edge-coloring of outerplanar graphs by showing the following results.

In [2], the authors pointed out that the constant 12 in Theorem 5.1(a) can be decreased to 9 by using more involved analysis. Moreover, they put forward the following conjecture.

Wang, Wang, and Wang [42] improved Theorem 5.1(a) by edge partition method.

A cactus is a graph in which every edge belongs to at most one cycle. Since these graphs are outerplanar, in order to prove Conjecture 5.2, it is worth to study the star edge coloring of cactus graphs. Omoomi, Dastjerdi, and Yektaeian [37] proved Conjecture 5.2 for cactus graphs.

An outerplanar graph $G$ is maximal if $G+uv$ is not outerplanar for any two non-adjacent vertices $u$ and $v$ of $G$. Deng and Tian [14] determined the exact values of the star chromatic index for all maximal outerplanar graphs with order $3\leq n\leq 8$ and proved the following results.

Recently, Deng, Yao, Zhang, and Cui [10] studied the star chromatic index of 2-connected outerplanar graphs and proved that if $G$ is a 2-connected outerplanar graph with diameter $d$ and maximum degree $\Delta$, then $\chi^{\prime}_{st}(G)\leq\Delta+6$ if $d=2$ or $3$; $\chi^{\prime}_{st}(G)\leq 9$ if $\Delta=5$.

Wang, Wang, and Wang [42] investigated the star edge-coloring of planar graphs by using an edge-partition technique and a useful relation between star chromatic index and strong chromatic index.

From the definitions, it is straightforward to see that $\chi^{\prime}_{st}(G)\leq\chi^{\prime}_{s}(G)$.

Using Theorems 5.9 and 5.10, currently the best bound for planar graphs can be obtained.

Similarly, Wang, Wang, and Wang [42] proved more specific results (together with the result for outerplanar graphs from Theorem 5.3).

A natural generalization of star edge-coloring is the list star edge-coloring. Given a list assignment $L$ which assigns to each edge $e$ a finite set $L(e)$, a graph is said to be $L$-star edge-colorable if $G$ has a star edge-coloring $c$ such that $c(e)\in L(e)$ for each edge $e$. The list-star chromatic index, $ch^{\prime}_{st}(G)$ of a graph $G$ is the minimum $k$ such that for every edge list $L$ for $G$ with $|L(e)|=k$ for every $e\in E(G)$, $G$ is $L$-star edge-colorable. For any graph $G$, it is obvious that $\chi^{\prime}_{st}(G)\leq ch^{\prime}_{st}(G)$.

Moser and Tardos [34] designed an algorithmic version of Lovász Local Lemma by means of the so-called Entropy Compression Method. In [7], by employing Entropy Compression Method, Cai, Yang, and Yu gave an upper bound for the list-star chromatic index of a graph.

Dvořák, Mohar, and Šámal [9] asked the following question.

Kerdjoudj, Kostochka, and Raspaud [20] gave a partial answer to this question. They proved that $ch^{\prime}_{st}(G)\leq 8$ for every subcubic graph. Subsequently, Lužar, Mockovčiaková, and Soták [31] answered Question 6.2 in affirmative.

Kerdjoudj, Kostochka, and Raspaud [20], Kerdjoudj and Kostochka [21] and Kerdjoudj, Pradeep, and Raspaud [22] studied the list star edge-coloring of graphs with small maximum average degree.

In [30], Li, Horacek, Luo, and Miao presented, in contrast, a best possible linear upper bound for the list-star chromatic index for some graph classes. Specifically they showed the following.

To overcome some difficulties in the proof, they developed a new coloring extension method by requiring certain edges to be colored with different size of sets of colors.

It was observed in [3] that every planar graph with girth $g$ satisfies $\text{mad}(G)<\frac{2g}{g-2}$. This implies the following by Theorems 3.4, 6.4, and 6.5.

For planar graphs with girth $4$, Li, Horacek, Luo, and Miao [30] obtained an infinite family of such graphs whose list-star chromatic index can not be bounded above by $\frac{3}{2}\Delta+c$.

In view of Theorem 5.12(c), Corollary 6.6(g) and Proposition 6.7, Li, Horacek, Luo, and Miao [30] conjectured that

Let $k\in\mathbb{N}$. A graph $G$ is $k$-degenerate if $\delta(H)\leq k$ for every subgraph $H$ of $G$. Kerdjoudj and Raspaud [23] and Han, Li, Luo, and Miao [16] proved:

Kerdjoudj and Raspaud [23] also considered the class of $K_{4}$-minor free graphs. Since the $K_{4}$-minor free graphs are 2-degenerate[15], by applying Theorem 6.9 we have $ch^{\prime}_{st}(G)\leq 4\Delta-2$ for any graph $G$ which is $K_{4}$-minor free and contains at least one edge. Kerdjoudj and Raspaud [23] improved this bound by proving the following.

Notice that Theorem 6.11 implies that Conjecture 3.2 is true for every $K_{4}$-minor free subcubic graph.

Han, Li, Luo, and Miao [16] extended this result of the star chromatic index of trees to list-star chromatic index.