Star 5-edge-colorings of subcubic multigraphs
Hui Lei Yongtang Shi Zi-Xia Song Tao Wang
math.CO

Wigner tomography of multispin quantum states
    Steffen J. Glaser
    January 15, 2018
=============================================


The star chromatic index  of a multigraph G, denoted
χ'_s(G),  is the minimum number of colors needed to properly
color the edges of G such that no path or cycle of length four is
bi-colored.  A multigraph G is star k-edge-colorable if
χ'_s(G)≤ k.   Dvořák, Mohar and Šámal [Star
chromatic index,  J. Graph Theory  72 (2013), 313–326]
proved  that every  subcubic multigraph is star 7-edge-colorable, and  conjectured  that every  subcubic multigraph
should be star 6-edge-colorable.       Kerdjoudj, Kostochka  and Raspaud  considered the list version of this problem for simple graphs and proved that every subcubic graph with maximum average degree  less than 7/3 is  star list-5-edge-colorable. It is known that  a graph with maximum average degree 14/5  is not necessarily  star 5-edge-colorable. In this paper, we  prove that every subcubic multigraph  with maximum average degree  less than 12/5 is star 5-edge-colorable.  


Keywords: star edge-coloring; subcubic multigraphs; maximum average degree

AMS subject classification 2010: 05C15 





§ INTRODUCTION


17pt


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)→ [k] be a proper
edge-coloring of G, where k≥1 is an integer and [k]:={1,2, …, k}. We say that
c is a  star k-edge-coloring of G if no path or cycle of
length four in G is bi-colored 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 χ'_s(G),  is the smallest integer k such that G is
star k-edge-colorable.  
As pointed out in  <cit.>, 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 <cit.>, motivated by the
vertex version (see <cit.>).   Given a multigraph G, we use  |G| to denote the number of vertices,  e(G) the number of edges, δ(G) the minimum degree, and Δ(G) the maximum degree of G, respectively.  
We use K_n and P_n to denote the complete graph and the path on n vertices, respectively.  A multigraph G is subcubic if all its vertices have degree less than or equal to
three. The maximum average degree of  a multigraph G, denoted  mad(G), is defined as the maximum  of  2
e(H)/|H| taken over all the subgraphs H of G.  The following upper bound is a result of  Liu and Deng <cit.>.  



For any graph  G with  Δ(G)≥7,
χ'_s(G)≤⌈16(Δ(G)-1)^3/2⌉.


Theorem <ref>  below is a result of Dvořák, Mohar and Šámal <cit.>,   which gives an   upper and a lower bounds for complete graphs.


  The star chromatic index of   the complete graph K_n satisfies


    2n(1+o(1))≤χ'_s(K_n)≤ n 2^2√(2)(1+o(1))√(log n)/(log n)^1/4.

In particular, for every ϵ>0, there exists a constant c such that  χ'_s(K_n)≤ cn^1+ϵ for every integer n≥1.


The true order of magnitude of  χ'_s(K_n) is still unknown. From Theorem <ref>,  an upper bound in terms of the maximum degree for general  graphs is also derived in <cit.>, i.e.,
χ'_s(G)≤Δ· 2^O(1)√(logΔ) for  any  graph G with maximum degree Δ.  In the same paper, Dvořák, Mohar and Šámal <cit.> also 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)→ V(H) such that for any uv∈ E(G), f(u)f(v)∈ E(H), and for any u∈ V(G), f is a bijection between N_G(u) and N_H(f(u)).  They proved the following.

 Let G be a multigraph.


  * If G is  subcubic,  then χ'_s(G)≤7.



  * If G is  cubic and has no multiple edges, then χ'_s(G)≥4 and the equality holds if and only if G covers the graph of 3-cube.



As observed in <cit.>,  K_3,3 is  not star 5-edge-colorable but star 6-edge-colorable. No subcubic multigraphs with star chromatic index seven  are known. Dvořák, Mohar and Šámal <cit.>   proposed the following conjecture.



Let G be a subcubic multigraph. Then χ'_s(G)≤ 6.


  It was  shown in <cit.> that every subcubic outerplanar graph is star 5-edge-colorable.
 Lei, Shi and Song <cit.> recently proved that every subcubic multigraph G with mad(G)<24/11 is star 5-edge-colorable, and  every subcubic multigraph G with mad(G)<5/2 is star 6-edge-colorable. Kerdjoudj,  Kostochka and Raspaud <cit.> considered the list version of star edge-colorings of simple graphs. They proved that every subcubic graph is   star list-8-edge-colorable, and further proved the following stronger results.
 Let G be a subcubic graph.


  * If mad(G)<7/3, then G is  star list-5-edge-colorable.


  * If mad(G)<5/2, then G is  star list-6-edge-colorable.





 
As mentioned above,   K_3,3 has star chromatic index 6, and is  bipartite and non-planar.  The graph, depicted in Figure <ref>,  has star chromatic index 6, and is planar and  non-bipartite.  We see that not every bipartite, subcubic graph is star 5-edge-colorable; and not every planar, subcubic graph is star 5-edge-colorable. It remains unknown whether every bipartite, planar subcubic multigraph is star 5-edge-colorable.  
In this paper, we improve Theorem <ref>(a) by showing the following main result.

  Let G be a subcubic multigraph with mad(G)<12/5. Then χ'_s(G)≤ 5.


  We don't know if the bound 12/5  in Theorem <ref> is best possible.  The graph depicted  in Figure <ref>  has  maximum average degree 14/5  but is not star 5-edge-colorable.  

The  girth of a graph G is the length of a shortest cycle in G.  It was observed in <cit.> that  every planar graph with girth g satisfies mad(G)< 2g/g-2.   This, together with Theorem <ref>,  implies the following.


Let G be a planar subcubic graph with girth g. If g≥12, then χ'_s(G)≤ 5.

 We need to introduce more notation. Given a multigraph G,
 a vertex of degree k  in G is a k-vertex, and a k-neighbor of a vertex v  in G is a k-vertex adjacent to v in G.  A 3_k-vertex in G
is a 3-vertex  incident to exactly k edges e in G such that the other end-vertex  of e is a 2-vertex. For any proper edge-coloring  c of a multigraph G and for any u∈ V(G), let c(u) denote the set of all colors such that each is used to color an edge incident with u under the coloring c.


For any two sets  A, B,   let  A B := A-B.   If  B={b}, we simply write  A b instead of A B. 


















§ PROPERTIES OF STAR 5-CRITICAL SUBCUBIC MULTIGRAPHS 


A  multigraph G is  star 5-critical if χ'_s(G)>5 and  χ'_s(G-v)≤ 5 for any v∈ V(G). In this section,  we establish some structure results on star 5-critical subcubic multigraphs.   Clearly, every star 5-critical multigraph  must be connected.


Throughout the remainder  of this section, let G be a star 5-critical subcubic multigraph, 
and let N(v) and d(v) denote the neighborhood and  degree of a vertex v in G, respectively.  Since every multigraph with maximum degree at most  two or  number of vertices at most four  is star 5-edge-colorable, we see that  Δ(G)=3  and |G|≥5.  As observed in <cit.>, any 2-vertex in G must have  two distinct neighbors.  The following Lemma <ref> and Lemma <ref> are proved in <cit.> and will be used in this paper.   








 For any 1-vertex x in G,  let  N(x)={y}. The following are true.


  * |N(y)|=3. 


  * N(y) is an independent set in G,  d(y_1)=3 and d(y_2)≥ 2, where N(y)={x, y_1,y_2} with   d(y_1)≥ d(y_2).


  * If d(y_2)=2, then for any i∈{1,2} and any v∈ N_G(y_i) y,   |N(v)|≥2, |N(y_1)|=3, |N(y_2)|=2,  and N[y_1]∩ N[y_2]={y}.


  * If d(y_2)=2, then  d(w_1)=3, where w_1 is the other neighbor of y_2 in G.


  * If  d(y_2)=3, then either d(v)≥2 for any v∈ N(y_1) or d(v)≥2 for any v ∈ N(y_2).





 
For any 2-vertex x in G,  let   N(x)={z, w} with |N(z)|≤ |N(w)|. The following are true.


  * If zw∈ E(G), then   |N(z)|=|N(w)|=3 and d(v)≥2 for any v∈ N(z)∪ N(w).


  * If  zw∉ E(G), then  |N(w)|=3 or  |N(w)|=|N(z)|=2,  and d(w)=d(z)=3.


  * If d(z)=2 and  z^*w∈ E(G),  then   |N(z^*)|=|N(w)|=3, and d(u)=3 for any u∈ (N[w] ∪ N[z^*]){x,z}, where z^* is the other neighbor of z in G.



  * If 
d(z)=2, then  |N(z^*)|=|N(w)|=3, and |N(v)|≥2 for any v∈ N(w)∪ N(z^*), where N(z)={x, z^*}.




Let H be the graph obtained from G by deleting all 1-vertices.     By Lemma <ref>(a,b), H is connected and  δ(H)≥2.  Throughout the remaining of the proof,  a 2-vertex   in H is bad if  it has a  2-neighbor  in H, and a 2-vertex   in H is good if  it is not bad.  For any 2-vertex r in H, we use r' to denote the unique 1-neighbor of r in G if d_G(r)=3. By Lemma <ref>(a) and the fact that  any 2-vertex in G has two distinct neighbors in G, we obtain the following two lemmas.


 
 For any 2-vertex x in H,  |N_H(x)|=2.
 


 
 For any 3_k-vertex   x in H with k≥2,  |N_H(x)|=3.
 


Proofs of Lemma <ref> and Lemma <ref> below can be obtained  from the proofs  of Claim 11  and   Lemma 12 in <cit.>, respectively. Since a star 5-critical multigraph is not necessarily the edge minimal counterexample in the proof of  Theorem 4.1 in <cit.>,   we include new proofs of  Lemma <ref> and Lemma <ref> here for completeness.


 
H has no 3-cycle such that  two of its  vertices  are bad.


Suppose that H does contain a 3-cycle with vertices x, y, z   such that both y and z are bad.  Then x must be a 3-vertex  in G because G is 5-critical. Let w be the third neighbor of x in G. Since G is 5-critical,  let c: E(G{y,z})→ [5] be any star 5-edge-coloring of G{y,z}.  Let α and β be two distinct numbers in [5] c(w) and γ∈ [5]{α, β, c(xw)}. Now coloring the edges xy, xz, yz  by colors  α, β, γ  in order,  and further  coloring all   the edges yy', zz' by color c(xw) if y' or  z' exists,  we obtain a star 5-edge-coloring of G, a contradiction. 
 height3pt width6pt depth2pt


    H has no 4-cycle  with vertices  x,u,v,w in order  such that all of u,v,w are  bad. Furthermore, if H contains a path with vertices x,u,v,w,y in order such that all of  u, v,w are  bad, then both x and y are 3_1-vertices in H.



Let P be a path   in H with  vertices x,u,v,w,y in order such that all of  u, v,w are  bad, where x and y may be the same.  Since all of  u, v,w are bad, by the definition of H, uw∉ E(G).
  By Lemma <ref>(b,c,e) applied to the vertex v,  d_G(v)=2.  By Lemma <ref>(b) applied to v,   d_G(u)=d_G(w)=3. Thus both w' and  u' exist.  Now by Lemma <ref>(c) applied to u' and w',  d_H(x)=d_H(y)=3, and x y. This proves  that H has no 4-cycle  with vertices  x,u,v,w in order  such that all of u,v,w are  bad.  


We next show that both x and y are 3_1-vertices in H. Suppose that one of x and y, say y, is not a   3_1-vertex in H.  Then  y is either a 3_2- vertex or 3_3-vertex   in H.  By Lemma <ref>,  |N_H(y)|=3.  Let N_H(y)={w,y_1,y_2} with d_H(y_1)=2. Then  y_1≠ u, otherwise H would have a 4-cycle with vertices  y,u,v,w in order  such that all of u,v,w are  bad.  Note that y_2 and x are not necessarily distinct.
By Lemma <ref>, let  r be the other neighbor of y_1 in H. Since G is 5-critical,  let c: E(G{v,u',w'})→ [5] be any star 5-edge-coloring of G{v,u',w'}. We may assume that c(wy)=3, c(yy_1)=1 and c(yy_2)=2. We first color  uv by a color α in [5] (c(x)∪{3}) and uu' by a color β in [5] (c(x)∪{α}).
Then 3∈ c(y_1)∩ c(y_2), otherwise, we may assume that 3∉ c(y_i) for some i∈{1,2}, now coloring vw by a color γ in {i,4,5}α and  ww' by a color in {i,4,5}{α,γ}
yields a star 5-edge-coloring of G, a contradiction. It follows that  4, 5∈ c(y_1)∪ c(y_2), otherwise, say θ∈{4,5} is not in c(y_1)∪ c(y_2), now recoloring wy by color θ, uv by a color α' in {α,β}θ, uu' by {α,β}α', and then coloring ww' by a color in {1,2}α' and vw by a color in {3,9-θ}α', we obtain a star 5-edge-coloring of G, a contradiction.  Thus c(y_1)={1,3,θ} and   c(y_2)={2,3,9-θ}, where θ∈{4,5}.  If c(y_1y_1')≠3 or c(y_1r)=θ and 1∉ c(r), then we obtain a star 5-edge-coloring of G by recoloring wy by color θ, uv by a color α' in {α,β}θ,  uu' by {α,β}α', and then coloring ww' by a color γ in {2,3,9-θ}α',  and vw by a color in {2,3,9-θ}{α',γ}.
Therefore,  c(y_1y_1')=3 and 1∈ c(r). Now recoloring y_1y_1' by a color in {2,9-θ} c(r),  we obtain a star 5-edge-coloring c of G{v,u',w'} satisfying c(wy)=3, c(yy_1)=1   and c(yy_2)=2 but 3∉ c(y_1)∩ c(y_2), a contradiction.  Consequently,  each of  x and y must be a  3_1-vertex in H. This completes the proof of Lemma <ref>.  height3pt width6pt depth2pt








   For any 3_3-vertex u in H,  no vertex in N_H(u) is  bad.
 

 Let N_H(u)={ x, y, z} with  d_H(x)=d_H(y)=d_H(z)=2. By Lemma <ref>, u,x,y,z are all distinct.    By Lemma <ref>, let x_1,  y_1 and z_1 be  the other neighbors of x, y, z in H, respectively. Suppose that  some vertex, say x, in N_H(u)  is bad. Then d_H(x_1)=2.  By Lemma <ref>, let w be the other neighbor  of x_1 in H.
 By Lemma <ref> and Lemma <ref>, N_H(u) is an independent set and x_1∉{y, z,y_1, z_1}.    Notice that  y_1,  z_1  and w  are not necessarily distinct.   Let A:={x} when d_G(x_1)=2 and A:= {x,x_1'} when  d_G(x_1)=3.    Let c: E(G A)→ [5] be any star 5-edge-coloring of G A.  We may assume that  c(uy)=1 and  c(uz)=2. We next prove  that 


(*)   1 ∈ c(y_1) and 2∈ c(z_1).

  Suppose that  1 ∉ c(y_1) or 2∉ c(z_1), say the former.
 If c(w) ∪{1,2}  [5],  then we obtain a star 5-edge-coloring of G  from c by coloring the remaining edges of G as follows (we only consider the worst scenario when  both x' and x_1'  exist):
 color the edge xx_1 by a color α in [5]  (c(w) ∪{1,2}),  x_1x_1' by a color β in [5]  (c(w) ∪{α}), ux by a color γ in [5] {1,2, α, c(zz_1)} and xx' by a color in [5] {1,2, α, γ}, a contradiction. Thus  c(w) ∪{1,2}= [5]. Then  c(w)={3,4,5}. We may assume that  c(x_1w)=3.   If  c(z) ∪{1,3} [5], then {4,5} c(z)∅ and we obtain a star 5-edge-coloring of G  from c  by coloring  the edge xx_1 by  color  2, x_1x_1' by color 1, ux by a color α in {4,5} c(z)   and xx' by a color in  {4,5}α, a contradiction.
 Thus c(z) ∪{1,3} = [5] and so c(z) ={2,4,5}. In particular,  z' must exist. We again obtain a star 5-edge-coloring of G  from c  by coloring  ux,xx', xx_1, x_1x_1' by colors 3, c(zz_1), 2,1 in order and then recoloring uz,zz' by colors c(zz'),2 in order,
 
 a contradiction.  Thus 1 ∈ c(y_1) and 2∈ c(z_1). This proves (*).   


  By (*),   1 ∈ c(y_1) and 2∈ c(z_1).  Then y_1 z_1,  and c(yy_1), c(zz_1)∉{1,2}. We may further assume that    c(zz_1)=3.  Let  α, β∉  c(z_1) and let   γ, λ∉  c(y_1), where α, β,  γ, λ∈ [5].  Since α, β∉  c(z_1), we may assume that c(yy_1)α.
  We may further assume that γα. If λα or γ∉{3,β},
   
    then we obtain a star 5-edge-coloring, say c', of  G A from c by recoloring the edges uz, zz', uy, yy' by colors α, β, γ, λ, respectively. Then  c' is a star 5-edge-coloring of  G A with c'(uz)∉ c'(z_1),  contrary to (*).  Thus  λ=α and  γ∈{3,β}.  By (*), 1∈ c(y_1) and so  α=λ1 and  γ1.
  
  Let c' be obtained from c by recoloring the edges uz, zz',  yy' by colors α, β, γ, respectively. Then  c' is a star 5-edge-coloring of  G A with c'(uz)∉ c'(z_1), which again contradicts (*). 

  This completes the proof of Lemma <ref>. height3pt width6pt depth2pt

 For any  3-vertex u in H with N_H(u) = {x, y, z}, if  both x and y are bad, then zx_1, zy_1∉ E(H),
and z must be a 3_0-vertex in H, where x_1 and y_1 are the other neighbors of x and y in H, respectively.



 Let u, x, y, z, x_1, y_1 be given as in the statement.    Since  d_H(x)=d_H(y)=2, by Lemma <ref>, u, x, y, z  are all distinct.   By Lemma <ref>,  d_H(z)=3.  Clearly,  both x_1 and y_1 are bad and so z x_1, y_1. By Lemma <ref>, xy∉ E(G)  and so  N_H(u) is an independent set in H.
 By Lemma <ref>,   x_1 y_1.  It follows that u, x, y, z, x_1, y_1 are all distinct.
We first show that zx_1, zy_1∉ E(H).   Suppose that zx_1∈ E(H) or  zy_1∈ E(H), say the latter.  Then zy_1 is not a multiple edge because d_H(y_1)=2.    Let   z_1 be the third neighbor of z in H.  By Lemma <ref>, let  v be the other neighbor of x_1 in H. Then v y_1.  Notice that  x_1 and z_1  are not necessarily distinct.   Let A={u, x, y, y_1, x_1'}. 
Since G is 5-critical,  let c: E(G A)→ [5] be any star 5-edge-coloring of G A.  We may assume that 1,2∉ c(z_1) and c(zz_1)=3. Let α∈ [5]( c(v)∪{1}) and β∈ [5](c(v)∪{α}). Then we obtain a star 5-edge-coloring of G from c  by  first coloring the  edges uz, zy_1, xx_1, x_1x_1' by colors 1, 2,α, β in order, and then coloring ux by a color γ in [5]{1,α,β,c(x_1v)}, xx' by a color in [5]{1,α,γ,c(x_1v)}, uy by a color θ in [5]{1,2,3, γ}, yy_1 by a color μ in [5]{1,2,γ,θ}, yy' by a color in [5]{2,γ,θ,μ}, y_1y_1' by a color in [5]{1,2, μ}, a contradiction. 
 

This proves that    zx_1, zy_1∉ E(H).


It remains to show that z must be a 3_0-vertex in H.  Suppose that z is not a 3_0-vertex in H. Since d_H(u)=3, we see that z is either a 3_1-vertex or a 3_2-vertex in H.
Let N_H(z)={u,s,t} with d_H(s)=2.  By Lemma <ref> applied to the vertex s,  s t. Since zx_1, zy_1∉ E(H), we see that x_1, y_1, s,t are all distinct. By Lemma <ref>, let v, w, r be the other neighbor of x_1, y_1, s in H, respectively.  
Note  that r, t, v, w are not necessarily distinct. By Lemma <ref>, both v and w must be  3-vertices in H. We next prove that  

(a)    if x' or y' exists, then for  any star 5-edge-coloring c^*  of G{x', y'},  c^*(xx_1)∈ c^*(v) or c^*(yy_1)∈ c^*(w).

To see why  (a) is true, suppose that there exists a star  5-edge-coloring c^*: E(G{x', y'})→ [5] such that c^*(xx_1)∉ c^*(v) and  c^*(yy_1)∉ c^*(w).  Then we obtain a star 5-edge-coloring of G from c^*  by  coloring  xx' by a color in [5]({c^*(xx_1)}∪ c^*(u)) and yy' by a color in [5]({c^*(yy_1)}∪ c^*(u)), a contradiction. This proves (a). 


Let A be the set containing x, y  and the  1-neighbor of  each of x_1, y_1 in G if it exists.    Since G is 5-critical,  let c_1: E(G A)→ [5] be any star 5-edge-coloring of G A.  Let c be a star 5-edge-coloring of G{x,  x', y', x_1'} obtained from c_1 by  coloring  yy_1 by a color α in [5] (c_1(w)∪{c_1(uz)}),    uy by a color  in [5](c_1(z)∪{α}), and  y_1y_1'  by a color β in [5] (c_1(w)∪{α}).  We may assume that c(uz)=1, c(zs)=2 and c(zt)=3. By the choice of c(uy), we may further assume that
c(uy)=4. We next obtain a contradiction  by extending c to be a   star  5-edge-coloring of G  (when neither of  x' and y'  exists) or a star 5-edge-coloring of G{x', y'} (when x' or y' exists)  which violates (a).  We consider the worst scenario when x' and  y' exist.  We first prove two claims. 



Claim 1:  β=4 or  c(y_1w)=4.



 Suppose that β 4 and c(y_1w)4.  We next show  that c(v)∪{1,4} [5]. Suppose that c(v)∪{1,4}= [5]. Then c(v)={2,3,5}. Clearly,   c(x_1v)=5, otherwise, coloring ux, xx_1,   x_1x'_1 by colors  5,1,4 in order,  we obtain    a star 5-edge-coloring of G{x', y'}  which violates (a), a contradiction.   
We see that   1∈ c(s)∩ c(t), otherwise,  we may assume  that   1∉ c(s), we obtain   a star 5-edge-coloring of G{x', y'}  which violates (a) as follows:  when  α2, color ux, xx_1, x_1x_1'  by colors 2, 4,1 in order; when α=2,  first color ux, xx_1, x_1x_1' by  colors 2, 4,1 in order and then  recolor  yy_1, y_1y_1' by colors β,2 in order.  It follows that  4, 5∈ c(s)∪ c(t), otherwise,   say θ∈{4,5} is not in c(s)∪ c(t),  let α'∈{2,3}α, now either  coloring ux, xx_1, x_1x_1' by colors α', 4,1 in order and  then recoloring  uz by color 5 when θ=5; or  coloring ux, xx_1, x_1x_1' by colors α', 1, 4 in order and then recoloring  uz, uy by colors 4, 1 in order when θ=4,
 we obtain  a star 5-edge-coloring of G{x', y'}  which violates (a).  Thus c(s)={1,2,θ} and   c(t)={1,3,9-θ}, where θ∈{4,5}.
  If  c(ss')=θ  or c(sr)= θ  and 2∉ c(r), then we obtain  a star 5-edge-coloring of G{x', y'} (which violates (a)) as follows: when θ=5,  color ux, xx_1, x_1x_1' by colors 3,1,4 in order  and then recolor  uz by color 5; when θ=4 and α∈{2,5}, first  color  ux, xx_1, x_1x'_1   by colors 3, 1, 4 in order, and then   recolor  uz, uy by colors 4, 1 in order;
  when θ=4 and α=3 and β 5,  color  ux, xx_1, x_1x'_1   by colors 5, 1, 4 in order and then   recolor  uz, uy, yy_1, y_1y_1' by colors 4, 3, β, 3 in order;  when θ=4 and α=3 and β=5,  color  ux, xx_1, x_1x'_1   by colors 3, 1, 4 in order and then   recolor  uz, uy, yy_1, y_1y_1' by colors 4, 1, 5, 3 in order.
 Thus   c(ss')=1, c(sr)=θ and 2∈ c(r).  Now recoloring the edge ss' by a color in {3,9-θ} c(r)  yields a star 5-edge-coloring c of G{x,  x', y', x_1'} satisfying β 4, c(y_1w)4,  c(v)∪{1,4}= [5] and c(x_1v)=5 but   1∉ c(s)∩ c(t), a contradiction. This proves that  c(v)∪{1,4} [5]. 




Since c(v)∪{1,4} [5], we see that [5] (c(v)∪{1,4})= {5}, otherwise, coloring ux by color 5,  xx_1 by a color γ in [5](c(v)∪{1,4,5}), and  x_1x'_1 by  a color in [5] (c(v)∪γ), we obtain a star 5-edge-coloring of G{x', y'} which violates (a).  Clearly, 2,3∈ c(v) and {1,4} c(v)∅. Let γ∈{1,4} c(v) and   α'∈{2,3}α.
Then   1∈ c(s)∩ c(t), otherwise,  we may assume  that   1∉ c(s), now      coloring ux, xx_1, x_1x_1' by colors 2, 5,γ in order  yields   a star 5-edge-coloring of G{x', y'}  which violates (a).
It follows that  4, 5∈ c(s)∪ c(t), otherwise, say θ∈{4,5} is not in c(s)∪ c(t),  first recoloring uz by color θ and then  either  coloring ux, xx_1, x_1x_1' by colors α', 5,  γ in order and then recoloring uy by color 1 when θ=4; or coloring
ux, xx_1, x_1x_1' by colors α', 1, 5 in order when θ=5 and γ=1; or
coloring ux, xx_1, x_1x_1' by colors 1,4,5 in order  when  θ=5, γ=4 and c(x_1v)1; or coloring ux, xx_1, x_1x_1' by colors α',4,5 in order  when  θ=5, γ=4 and c(x_1v)=1,
we obtain a star 5-edge-coloring of G{x', y'}  which violates (a).
Thus c(s)={1,2,θ} and   c(t)={1,3,9-θ}, where θ∈{4,5}. If  c(ss')=θ  or c(sr)= θ  and 2∉ c(r), then we obtain  a star 5-edge-coloring of G{x', y'} (which violates (a)) as follows: when θ=5 and γ=1,  color ux, xx_1, x_1x_1' by colors 3, 1, 5 in order and then recolor  uz by colors 5;
when θ=5,  γ=4 and c(x_1v)1,  color ux, xx_1, x_1x_1' by color 1, 4, 5 in order and then recolor  uz by colors 5;
when θ=5,  γ=4 and c(x_1v)=1,  color ux, xx_1, x_1x_1' by color 3, 4, 5 in order and then recolor  uz by colors 5 (and  further recolor yy_1 by β and y_1y_1' by α when α=3);
when θ=4 and β1,  color ux, xx_1, x_1x_1' by color 3, 5, γ in order and then recolor  uz,  uy by colors  4, 1 in order,   and finally recolor yy_1 by a color  β'∈{α,β} 3 and  y_1y'_1 by a color in {α,β}β';
when θ=4,  β=1 and  γ=1,  color ux, xx_1, x_1x_1' by color 5,1,5 in order and then recolor  uz,  uy, yy_1, y_1y_1' by colors  4, 3, 1, α in order;
when θ=4,  β=1,   γ=4 and α3,  color ux, xx_1, x_1x_1' by color 3, 5, 4 in order and then recolor  uz,  uy by colors  4, 1 in order;
when θ=4,  β=1,   γ=4 and α=3, let γ'∈{1,3} c(x_1v),  color ux, xx_1, x_1x_1' by color γ', 5, 4 in order and then recolor  uz by color 4,  uy by color  5,  yy_1 by a color β' in {1,3}γ' and  y_1y_1' by a color in {1,3}β'.
Thus c(ss')=1, c(sr)=θ and 2∈ c(r).  Now recoloring the edge ss' by a color in {3,9-θ} c(r)  yields a star 5-edge-coloring c of G{x,  x', y', x_1'}    satisfying β 4,  c(y_1w)4  and [5] (c(v)∪{1,4})= {5} but   1∉ c(s)∩ c(t), a contradiction.  This completes the proof of Claim 1.
 height3pt width6pt depth2pt



 Claim 2:  β=4.  


Suppose that  β 4. By Claim 1,  c(y_1w)=4.  We first consider the case when  c(w)={2,3,4}. Then  α=5 and β=1. We claim that
c(v)∪{1,4} [5]. Suppose that c(v)∪{1,4}= [5].
Then c(v)={2,3,5}. Clearly,  1∈ c(s)∩ c(t), otherwise,  we may assume that 1∉ c(s), now coloring ux, x x_1, x_1x'_1 by colors 5,4,1 in order and then  recoloring uy by 2,  we  obtain a star 5-edge-coloring of G{x', y'} which violates (a).
 It follows that  4, 5∈ c(s)∪ c(t), otherwise, say θ∈{4,5} is not in c(s)∪ c(t),  now coloring ux, x x_1, x_1x'_1 by colors 3,1,4 in order and then  recoloring uz,  uy, yy_1, y_1y_1' by colors θ, 2, 1,5 in order
we obtain a star 5-edge-coloring of G{x', y'}  which violates (a).
Thus c(s)={1,2,θ} and   c(t)={1,3,9-θ}, where θ∈{4,5}.
If  c(ss')=θ  or c(sr)= θ  and 2∉ c(r), then   coloring ux, x x_1, x_1x'_1 by colors 3,1,4 in order and then  recoloring uz,  uy, yy_1, y_1y_1' by colors θ, 9-θ, 1,5 in order yileds a star 5-edge-coloring of G{x', y'} which violates (a).
Thus c(ss')=1,  c(sr)= θ  and 2∈ c(r). Now recoloring the edge ss' by a color in {3,9-θ} c(r)  yields a star 5-edge-coloring c of G{x,  x', y', x_1'}  satisfying α=5, β=1, c(y_1w)=4 and  c(v)∪{1,4}= [5] but 1∉ c(s)∩ c(t), a contradiction. This proves that  c(v)∪{1,4} [5].
 Let η=5 when 5∉ c(v) or η∈{2,3} c(v)   when 5∈ c(v).  Let μ∈ [5]( c(v)∪{η}).  By Claim 1 and the symmetry between x and y, either 4∉ c(v) or 5∉ c(v). We see that   μ=4 when η 5.
  Then  1∈ c(s)∩ c(t), otherwise, we may assume 1∉ c(s), we obtain a star 5-edge-coloring of G{x', y'}  (which violates (a)) as follows: when  η≠ 2,  color ux, xx_1, x_1x_1' by colors 2, η, μ in order; when η=2, then μ=4,  first recolor uy by color 2 and  then color ux, xx_1, x_1x'_1 by colors  5,4,  2 in order.
It follows that  4, 5∈ c(s)∪ c(t), otherwise, say θ∈{4,5} is not in c(s)∪ c(t),
now first recoloring uz, yy_1, y_1y_1' by colors θ, 1,5  in order, and then coloring  xx_1, x_1x'_1 by colors η,μ in order,  ux by a color γ in [5]{μ,η,θ, c(x_1v)},  and finally  coloring uy either by a color in {2,3}η when  γ=1 or by a color in  {2,3}γ when γ1,
we obtain a star 5-edge-coloring of G{x', y'}  which violates (a).
Thus c(s)={1,2,θ} and   c(t)={1,3,9-θ}, where θ∈{4,5}.
If   c(ss')=θ  or c(sr)= θ  and 2∉ c(r), we obtain a star 5-edge-coloring of G{x', y'}  (which violates (a)) as follows:
when θ=4 and η=5, color ux, xx_1, x_1x_1' by colors 3, 5, μ in order and then recolor uz, uy by colors 4,1 in order;
when θ=4 and η∈{2,3}, then μ=4,  first recolor uz, uy by colors 4,3 in order and then color xx_1, x_1x_1' by colors η, 4 in order and finally color ux by a color γ in {1,5} c(x_1v), yy_1 by a color λ in {1,5}γ, and y_1y_1' by a color in {1,5}λ;
when θ=5 and η∈{2,3}, then μ=4, color ux, xx_1, x_1x_1' by colors 1, 4, η in order and then recolor uz, uy, yy_1, y_1y_1' by colors 5,3, 1,5 in order;
when θ=5,  η=5 and μ3, color ux, xx_1, x_1x_1' by colors 1, μ, 5 in order and then recolor uz, uy, yy_1, y_1y_1' by colors 5,3, 1,5 in order;
when θ=5,  η=5 and μ=3, first recolor uz, uy, yy_1, y_1y_1' by colors 5,3, 1,5 in order, then color xx_1, x_1x_1' by colors 5, 3 in order and  finally color ux by a color in {1,4} c(x_1v).
 Thus c(ss')=1, c(sr)= θ  and 2∈ c(r).  Now recoloring the edge ss' by a color in {3,9-θ} c(r)  yields a star 5-edge-coloring c of G{x,  x', y', x_1'}  satisfying α=5, β=1, c(z)={1,2,3}, c(uy)=c(y_1w)=4 and  c(v)∪{1,4}[5] but 1∉ c(s)∩ c(t), a contradiction.


We next consider the case when  c(w)≠{2,3,4}.
If α, β5, then recoloring uy by color 5 yields  a  star 5-edge-coloring c of G{x,  x', y', x_1'} with c(uy) c(y_1y_1'), c(y_1w),  contrary to  Claim 1. Thus either α=5 or  β=5.  Then 1∈ c(w) because c(w)≠{2,3,4} and |c(w)|=3.

It follows that α, β∈{2,3,5} and 5∈{α, β}. We may assume that α∈{2,3} and β=5 by permuting the colors on yy_1 and y_1y_1' if needed.  Then 4,5∈ c(s)∪ c(t), otherwise, say θ∈{4,5} is not in c(s)∪ c(t), we obtain a a star 5-edge-coloring c of G{x,  x', y', x_1'}  which contradicts Claim 1 by recoloring uz, uy by colors θ, 1 in order.  Let α'∈{2,3}α.  We next show that c(ss')=1,  c(sr)= θ  and 2∈ c(r).

Suppose first  that c(v)∪{1,4}= [5].
Then c(v)={2,3,5}. We see that  c(x_1v)=5, otherwise, coloring ux, xx_1, x_1x'_1 by colors  5,1,4 in order,  we obtain    a star 5-edge-coloring of G{x', y'}  which violates (a).  Clearly,  1∈ c(s)∩ c(t), otherwise,  we may assume that 1∉ c(s), now coloring ux, x x_1, x_1x'_1 by colors 2,4,1 in order and then  recoloring yy_1,y_1y_1' by colors 5,α, we  obtain a star 5-edge-coloring of G{x', y'} which violates (a).  Since 4,5∈ c(s)∪ c(t), we see that  c(s)={1,2,θ} and   c(t)={1,3,9-θ}, where θ∈{4,5}.
If  c(ss')=θ  or c(sr)= θ  and 2∉ c(r), then  recoloring uz, uy by colors θ, 1 in order  yields  a  star 5-edge-coloring c of G{x,  x', y', x_1'} with c(uy) c(y_1y_1'), c(y_1w),  contrary to  Claim 1.
Thus c(ss')=1,  c(sr)= θ  and 2∈ c(r).  Next suppose   that c(v)∪{1,4}  [5].
Let η=5 when 5∉ c(v) or η∈{2,3} c(v)   when 5∈ c(v).  Let μ∈ [5]( c(v)∪{η}). By Claim 1 and the symmetry between x and y, either 4∉ c(v) or 5∉ c(v). We see that   μ=4 when η 5.   Then  1∈ c(s)∩ c(t), otherwise, we may assume 1∉ c(s), we obtain a star 5-edge-coloring of G{x', y'}  (which violates (a)) as follows: when  η=5,  color ux, xx_1, x_1x_1' by colors 4, 5, μ in order and then recolor uy, yy_1, y_1y_1' by colors 2,5,α in order; when η∈{2,3}, then μ=4,  color ux, xx_1, x_1x'_1 by colors  5,η,  4 in order.  Since 4,5∈ c(s)∪ c(t), we see that  c(s)={1,2,θ} and   c(t)={1,3,9-θ}, where θ∈{4,5}.
If  c(ss')=θ  or c(sr)= θ  and 2∉ c(r), then  recoloring uz, uy by colors θ, 1 in order  yields  a  star 5-edge-coloring c of G{x,  x', y', x_1'} with c(uy) c(y_1y_1'), c(y_1w),  contrary to  Claim 1.
Thus c(ss')=1,  c(sr)= θ  and 2∈ c(r). 

Now recoloring the edge ss' by a color in {3,9-θ} c(r)  yields a star 5-edge-coloring c of G{x,  x', y', x_1'}  satisfying α∈{2,3}, β=5, c(y_1w)=4 and   c(w)≠{2,3,4} but 1∉ c(s)∩ c(t), a contradiction.   This completes the proof of Claim 2. height3pt width6pt depth2pt







By Claim 2, β=4.     Suppose that α5.  Then  α∈{2,3}.  Note that α∉ c(w)∪{1}. Now  recoloring uy by color 5, we obtain a star 5-edge-coloring c of G{x,  x', y', x_1'} satisfying c(uz)=1, c(zs)=2 and   c(zt)=3 but β c(uy), contrary to Claim 2. Thus α=5 and   so c(w)={1,2,3}.
 By the symmetry of x and y, c(v)={1,2,3}.  Then 1∈ c(s)∩ c(t), otherwise,   we may assume  that   1∉ c(s), now      coloring ux, xx_1, x_1x_1' by colors 2,5,4 in order  yields   a star 5-edge-coloring of G{x', y'}  which violates (a).  It follows that  4, 5∈ c(s)∪ c(t), otherwise,   say θ∈{4,5} is not in c(s)∪ c(t),   now first coloring ux, xx_1, x_1x_1' by colors 2,9-θ,  θ in order and then recoloring uz, uy, yy_1, y_1y_1' by colors θ, 3, 9-θ, θ in order, we obtain      a star 5-edge-coloring of G{x', y'}  which violates (a).  Thus c(s)={1,2,θ} and   c(t)={1,3,9-θ}, where θ∈{4,5}.  If c(ss')=θ or c(sr)=θ and 2∉ c(r), then we obtain  a star 5-edge-coloring of G{x', y'} (which violates (a)) by coloring ux, xx_1, x_1x_1' by colors 1, 9-θ, θ in order, and then  recoloring uz, uy, yy_1, y_1y_1' by colors θ, 3, 9-θ, θ in order.
Thus c(ss')=1 and   2∈ c(r). Now recoloring ss' by a color in {3,9-θ} c(r),  we obtain a star 5-edge-coloring c of G{x,  x', y', x_1'} satisfying c(uz)=1, c(zs)=2,  c(zt)=3, β= 4 and  α=5  but   1∉ c(s)∩ c(t). 


This completes the proof of Lemma <ref>.height3pt width6pt depth2pt












 

§ PROOF OF THEOREM <REF>





We are now ready to prove Theorem <ref>.  Suppose the  assertion is false. Let G be a subcubic multigraph with mad(G)<12/5 and  χ'_s(G)>5. Among all counterexamples we choose G so that
|G| is minimum. By the choice of G, G is connected,  star 5-critical,  and  mad(G)<12/5.  For all i∈[3], let A_i={v∈ V(G):   d_G(v)=i} and let  n_i=|A_i| for all i∈[3].
Since  mad(G)<12/5, we see that  3n_3<2n_2+7n_1 and so  A_1∪ A_2∅. By Lemma <ref>(a), A_1  is an  independent set in G and N_G(A_1)⊆ A_3.  Let H=G A_1.  Then H is connected and mad(H)<12/5. By Lemma <ref>(b), δ(H)≥2.  By Lemma <ref>, every  3_2-vertex   in H has three distinct neighbors in H.
We say that a 3_2-vertex   in H is bad if  both of its  2-neighbors  are bad.  A vertex u is a good (resp. bad) 2-neighbor of a vertex v in H  if uv∈ E(H) and u is a good (resp. bad) 2-vertex. By Lemma <ref>,  every bad 3_2-vertex in H has a unique 3_0-neighbor. We now  apply the discharging method to obtain a contradiction. 


For each vertex v∈ V(H), let ω(v):= d_H(v)-12/5 be the initial charge of v. Then ∑_v∈ V(H)ω(v) =2e(H)-12/5|H|=|H|(2e(H)/|H|-12/5)<0. Notice that for each v∈ V(H),  ω(v)=2-12/5=-2/5 if d_H(v)=2,  and ω(v)=3-12/5=3/5 if d_H(v)=3. We will redistribute the  charges of vertices in  H as follows. 

(R1):  every bad 3_2-vertex in H takes  1/5 from its unique 3_0-neighbor.

(R2): every 3_1-vertex in H gives 3/5 to its  unique 2-neighbor.

(R3):  every  3_2-vertex  in H gives  1/5 to each of its good 2-neighbors (possibly none) and 2/5 to each of its bad 2-neighbors (possibly none).

(R4): every 3_3-vertex in H gives 1/5 to each of its 2-neighbors.

 Let ω^* be the new charge of H after applying the above discharging rules in order. It suffices to show that ∑_v∈ V(H)ω^*(v)≥0.
For any v∈ V(H) with d_H(v)=2, by Lemma <ref>, v has two distinct neighbors in H.
If v is a good 2-vertex, then v takes  at least 1/5 from each of its 3-neighbors under  (R2), (R3) and (R4), and so  ω^*(v)≥0.  Next, if  v is a bad 2-vertex, let x, y be the  two neighbors of v in  H. We may assume that  y is a bad 2-vertex. By Lemma <ref>, let z be the other  neighbor  of y in H.  By Lemma <ref>, we may assume that d_H(x)=3.  By Lemma <ref>, x is either a 3_1-vertex or a 3_2-vertex in H.  Under (R2) and (R3), v takes at least 2/5 from x.  If d_H(z)=3, then  by a similar argument,  y must take at least 2/5 from z.  In this case, ω^*(v)+ω^*(y)≥0.  If d_H(z)=2, then z is bad. By Lemma <ref>, let w be the other neighbor of z.  By Lemma <ref>, each of x and w must be a 3_1-vertex in H. Under (R2), v takes 3/5 from x and z takes 3/5 from w. Hence, ω^*(v)+ω^*(y)+ω^*(z)≥0. 

For any v∈ V(H) with d_H(v)=3, if v is a bad 3_2-vertex,  then   v has a unique 3_0-neighbor by Lemma <ref>. Under (R1) and (R3), v first takes 1/5 from its unique 3_0-neighbor and then gives 2/5 to each of its bad 2-neighbors, we see that  ω^*(v)≥0.  If  v is not a bad 3_2-vertex, then  v gives either nothing  or one of 1/5,  2/5,  and 3/5 in total to its neighbors under    (R1), (R2), (R3) and (R4). In either case,   ω^*(v)≥0.
Consequently,  ∑_v∈ V(H)ω^*(v)≥0, contrary to the fact that  ∑_v∈ V(H)ω^*(v)=∑_v∈ V(H)ω(v)<0. 

This completes the proof of Theorem <ref>.
height3pt width6pt depth2pt


  
 Acknowledgments.  Zi-Xia Song would like to thank Yongtang Shi and  the Chern Institute of Mathematics at Nankai University for hospitality and support during her visit  in May 2017. Hui  Lei and Yongtang  Shi are partially supported by the National Natural Science Foundation of China and the Natural Science Foundation of Tianjin (No.17JCQNJC00300). Tao  Wang is partially supported by the National Natural Science Foundation of China (11101125) and the Fundamental Research Funds for Universities in Henan (YQPY20140051).  
  
 




10

ACKKR2004
M. O. Albertson, G. G. Chappell, H. A. Kierstead,  A. Kündgen and  R. Ramamurthi, Coloring with no 2-colored P_4's, Electron. J. Combin.  11 (2004), #R26.




BLM2016
Ľ. Bezegová, B. Lužar, M. Mockovčiaková, R. Soták and
  R. Škrekovski, Star edge coloring of some classes of graphs, J. Graph
  Theory 81 (1) (2016) 73–82.




girth
O. V.  Borodin, A. V. Kostochka, J. Nešetřil,  A.  Raspaud and  E. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math.  206 (1999)  77–89.




BCMRW2009
Y. Bu, D. W. Cranston, M. Montassier, A. Raspaud and  W. Wang, Star coloring
of sparse graphs,  J Graph Theory  62  (2009) 201–219.




CRW2013
M. Chen, A. Raspaud and  W. Wang, 6-star-coloring of subcubic graphs,
J Graph Theory  72  (2013) 128–145.




DMS2013
Z. Dvořák, B. Mohar and R. Šámal, Star chromatic index, J
Graph Theory  72  (2013) 313–326.




KKP2017
S. Kerdjoudj, A. V. Kostochka and A. Raspaud, List star edge coloring of
  subcubic graphs, to appear in Discuss. Math. Graph Theory.




KKT2009
H. A.  Kierstead and  A.  Kündgen,  C. Timmons, Star coloring bipartite planar graphs, J Graph Theory  60  (2009) 1–10.




LSS2017
H. Lei, Y. Shi and Z-X. Song, Star chromatic index of subcubic multigraphs,
  to appear in J. Graph Theory.




DL2008 X.-S.  Liu and   K. Deng, An upper bound on the star chromatic index of
graphs with Δ≥7, J Lanzhou Univ (Nat Sci)  44  (2008) 94–95.




NM2003 J. Nešetřil and  P. Ossona de Mendez, Colorings and homomorphisms of minor closed classes,  Algorithms and Combinatorics, Vol. 25, Springer, Berlin, 2003, pp.    651–664.



