# The Linear 2- and 4-Arboricity of Complete Bipartite GraphKm,n

Authors: Liancui Zuo; Bing Xue; Shengjie He
Journal: International Journal of Combinatorics
 (2013)

---

## Abstract

A lineark-forest of an undirected graph G is a subgraph of G whose components are paths with lengths at most k. The linear k-arboricity of G, denoted by lak(G), is the minimum number of linear k-forests needed to decompose G. In case the lengths of paths are not restricted, we then have the linear arboricity of G, denoted by la(G). In this paper, the exact value of the linear 2- and 4-arboricity of complete bipartite graph Km,n for some m and n is obtained.


---

## Body

## 1. Introduction

Throughout this paper, all graphs considered are finite, undirected, and simple. Letℕ represent the set of natural numbers and let [a,b] denote the set {n∈ℕ∣a≤n≤b}. A graph G is m-partite (m≥2), if it is possible to partition the vertex set V(G) into m independent sets V1,V2,…,Vm (called partite sets) such that every edge of G joins the vertices in different partite sets. A complete m-partite graph is one that is simple and in which each vertex is joined to every vertex that is not in the same subset, which is denoted by Kn1,n2,…,nm if |Vi|=ni for i∈[1,m]. For m=2, such graphs are called complete bipartite graphs and denoted by Kn1,n2. When n1=n2=⋯=nm=n, we denote Kn1,n2,…,nm by Km(n), which is called balanced complete m-partite graph. For m=2, such graphs are called balanced complete bipartite graphs and are denoted by Kn,n. On the other hand, a graph with order n, in which any pair of different vertices are adjacent, is a complete graph, denoted by Kn. Other notations and terminology in the paper are the same as in [1].Adecomposition of a graph is a list of subgraphs such that each edge appears in exactly one subgraph in the list. If a graph G has a decomposition G1,G2,…,Gt, then we say that G1,G2,…,Gt decompose G or G can be decomposed into G1,G2,…,Gt. Furthermore, a linear k-forest is a forest whose components are paths of length at most k. The linear k-arboricity of a graph G, denoted by lak(G), is the least number of linear k-forests needed to decompose G.The notion of lineark-arboricity of a graph was first introduced by Habib and Peroche [2]. It is a natural generalization of edge coloring. Clearly, a linear 1-forest is induced by a matching, and la1(G) is the chromatic index χ′(G) of a graph G. Moreover, the linear k-arboricity lak(G) is also a refinement of the ordinary linear arboricity la(G) (or la∞(G)) which is the case when every component of each forest is a path with no length constraint. By the way, the notion of linear arboricity was introduced earlier by Harary in [3].In 1982, Habib and Péroche [4] proposed the following conjecture for an upper bound on lak(G).Conjecture 1 (see [4]).
IfG is a graph with maximum degree Δ(G) and k≥2, then(1)lak(G)≤{⌈Δ(G)|V(G)|2⌊k|V(G)|/(k+1)⌋⌉,whenΔ(G)=|V(G)|-1,⌈Δ(G)|V(G)|+12⌊k|V(G)|/(k+1)⌋⌉,whenΔ(G)<|V(G)|-1.Fork=|V(G)|-1, this is Akiyama’s conjecture [5].Conjecture 2 (see [5]).
Considerla(G)≤⌈(Δ(G)+1)/2⌉.So far, there have been a lot of results on the verification of Conjecture1 in the literature, especially for graphs with particular structures, such as trees [2, 6, 7], regular graphs [8, 9], planar graphs [10], and complete graphs [11–15]. The linear arboricity and the linear k-arboricity of cubic graphs are studied in recent years, and for more details, please read the papers [11, 16–20]. The linear  2-arboricity, the linear 3-arboricity and the low bound of linear k-arboricity of balanced complete bipartite graph, and linear 3-arboricity of the balanced complete multipartite graph in [13, 15, 21, 22], respectively, are obtained. In 2010, Xue and Zuo obtained the linear (n-1)-arboricity of Kn(m) in [23].As for a low bound onlak(G), since any vertex in a linear k-forest has degree at most 2 and a linear k-forest in a graph G has at most ⌊k·|V(G)|/(k+1)⌋ edges, the following result is obvious.Lemma 3 (see [15]).
For any graphG with maximum degree Δ(G),
(2)lak(G)≥max{⌈Δ(G)2⌉,⌈|E(G)|⌊k·|V(G)|/(k+1)⌋⌉}.It is clear that the following lemma holds.Lemma 4.
IfG=G1∪G2∪⋯∪Gn, then lak(G)≤lak(G1)+lak(G2)+⋯+lak(Gn).In the following, we will study the linear2- and 4-arboricity of the complete bipartite graph Km,n.


## 2. The Linear 2-Arboricity of Complete Bipartite GraphKm,n

Lemma 5.
Consider
la2(K4,2)=2 and la2(K4,3)=la2(K5,2)=3.Proof.
By Lemma3, la2(K4,2)≥2, la2(K4,3)≥3, and la2(K5,2)≥3.
LetK4,2=(V1,V2), where V1={vi:i∈[1,4]} and V2={u1,u2}. Clearly, K4,2 can be decomposed into two linear 2-forests: {v1u1v2,v3u2v4} and {v1u2v2,v3u1v4}. Thus la2(K4,2)=2.
LetK4,3=(V1′,V2′), where V1′={vi:i∈[1,4]} and V2′={uj:j∈[1,3]}. Clearly, K4,3 can be decomposed into three linear 2-forests: {v1u1v2,v3u2v4}, {v1u2v2,v3u3v4}, and {v1u3v2,v3u1v4}. Thus la2(K4,3)=3.
LetK5,2=(V1′′,V2′′), where V1′′={vi:i∈[1,5]} and V2′′={u1,u2}. Clearly, K5,2 can be decomposed into three linear 2-forests: {v1u1v2,v3u2v4}, {v1u2v2,v4u1v5}, and {v3u1,v5u2}. Thus la2(K5,2)=3.In the following, we mainly consider the complete bipartite graphsK4n,2n, K4n+1,2n, and K4n,2n+1 in this section.LetG(V1,V2) be a bipartite graph with partite sets V1={v10,v11,…,v1(r-1)} and V2={v20,v21,…,v2(s-1)}. Suppose that |V2|=s≥r=|V1|. In [15], Fu et al. defined the bipartite  difference of an edge v1pv2q in G(V1,V2) as the value (q-p)(mods). It is not difficult to see that a set consisting of those edges in G(V1,V2) with the same bipartite difference must be a matching. In particular, such a set is a perfect matching if G(V1,V2) is a Kn,n. Furthermore, we can partition the edge set of Kn,n into n pairwise disjoint perfect matchings M0,M1,…,Mn-1 such that Mi is exactly the set of edges of bipartite difference i in Kn,n for i∈[0,n-1].Theorem 6.
One hasla2(K4n,2n)=2n.Proof.
LetG(V1,V2)=K4n,2n be a complete bipartite graph with partite sets V1 and V2, where |V1|=4n and |V2|=2n. Next, we partition V1 and V2 into n vertex sets V1i and V2i, respectively, such that |V1i|=4 and |V2i|=2 for i∈[0,n-1].
For eachV1i(i∈[0,n-1]), we identify 4 vertices in V1i and denote a new vertex by v1[i]. For each V2i, we identify 2 vertices in V2i and denote a new vertex by v2[i]. Then we obtain a balanced complete bipartite graph H=Kn,n with vertex sets  V1′={v1[i]:i∈[0,n-1]} and V2′={v2[i]:i∈[0,n-1]}. The edge set of Kn,n can be partitioned into n pairwise disjoint perfect matchings M0,M1,…,Mn-1 such that Mj is exactly the set of edges of bipartite difference j in Kn,n for j∈[0,n-1]. Every edge in Mj corresponds to a subgraph of K4n,2n isomorphic to K4,2. Since la2(K4,2)=2 by Lemma 5, each Mj corresponds to two linear 2-forests in K4n,2n. Thus la2(K4n,2n)≤2n by Lemma 4. Applying Lemma 3, we have la2(K4n,2n)≥2n. Hence la2(K4n,2n)=2n.Corollary 7.
One hasla2(K4n,2n-1)=la2(K4n-1,2n)=2n.Proof.
The results can be obtained by Lemma3 and Theorem 6 immediately.Theorem 8.
l
a
2
(
K
4
n
,
2
n
+
1
)
=
2
n
+
1, where n is odd.Proof.
LetG(V1,V2)=K2n+1,4n be a complete bipartite graph with partite sets V1 and V2, where |V1|=2n+1 and |V2|=4n. Next, we partition V1 into n+1 vertex sets V1j(j∈[0,n]) and partition V2 into n vertex sets V2i(i∈[0,n-1]), respectively, such that |V1i|=2, |V2i|=4 for i∈[0,n-1], and |V1n|=|{u}|=1.
For eachV1i(i∈[0,n-1]), we identify 2 vertices in V1i and denote a new vertex by v1[i]. For each V2i(i∈[0,n-1]), we identify 4 vertices in V2i and denote a new vertex by v2[i]. Then we obtain a complete bipartite graph H=Kn+1,n with partite sets V1′={v1[i]:i∈[0,n-1]}∪{u} and V2′={v2[i]:i∈[0,n-1]}. Let H1(V,V2′)=Kn,n be a balanced complete bipartite graph with partite sets V=V1′∖{u}={v1[i]:i∈[0,n-1]} and V2′={v2[j]:j∈[0,n-1]}. Let H2=Kn,1 be a complete bipartite graph with vertex sets  V2′={v2[i]:i∈[0,n-1]} and {u}. In fact, H2=Kn,1 is a star Sn+1 with the center u. Thus, H=H1∪H2. Since the edge set of H1(V,V2′)=Kn,n can be partitioned into n pairwise disjoint perfect matchings M0,M1,…,Mn-1 such that Mj is exactly the set of edges of bipartite difference j in Kn,n for j∈[0,n-1] and n is odd, the edge set of H=Kn+1,n can be partitioned into n pairwise disjoint edge sets M0′,M1′,…,Mn-1′ such that Mj′=Mj∪{uv2[2j]}(j∈[0,n-1]) which consists of a 2-path uv2[2j]v1[j] and n-1 isolated edges v1[i]v2[i+j](i∈[0,j-1]∪[j+1,n-1]), where 2j,i+j are taken modulo n.
Thus, each edgev1[i]v2[i+j](i∈[0,j-1]∪[j+1,n-1]) in Mj′ corresponds to a subgraph isomorphic to K4,2 and the 2-path uv2[2j]v1[j] corresponds to a subgraph isomorphic to K4,3 with partition (V2(2j),V1j∪{u}) in K2n+1,4n. Let
(3)V1j={v1[j]0,v1[j]1},V2(2j)={v2[2j]0,v2[2j]1,v2[2j]2,v2[2j]3},
where the indices 2j are taken modulo n.
After taking away the four edgesv2[2j]0v1[j]0,v2[2j]1v1[j]0,v2[2j]2v1[j]1, and v2]2j]3v1[j]1 from each K4,3 to which the 2-path uv2[2j]v1[j] corresponds, each Mj′ corresponds to two linear 2-forests of K4n,2n+1 by Lemma 5. The edges that we take away form one linear 2-forest. Hence la2(K2n+1,4n)≤2n+1 by Lemma 4. Since la2(K2n+1,4n)≥2n+1 by Lemma 3, we have la2(K2n+1,4n)=2n+1.Corollary 9.
l
a
2
(
K
4
n
-
1,2
n
+
1
)
=
2
n
+
1, where n is odd.Proof.
The results can be obtained by Lemma3 and Theorem 8 immediately.Theorem 10.
l
a
2
(
K
4
n
+
1,2
n
)
=
2
n
+
1, where n is odd.Proof.
The proof is similar to Theorem8. Let G(V1,V2)=K4n+1,2n be a complete bipartite graph with partite sets V1 and V2, where |V1|=4n+1 and |V2|=2n. Next, we partition V2 into n vertex sets V2i(i∈[0,n-1]) and partition V1 into n+1 vertex sets V1i(i∈[0,n]), respectively, such that |V2i|=2, |V1i|=4 for i∈[0,n-1], and |V1n|=|{u}|=1.
For eachV1i(i∈[0,n-1]), we identify 4 vertices in V1i and denote a new vertex by v1[i]. For each V2i(i∈[0,n-1]), we identify 2 vertices in V2i and denote a new vertex by v2[i]. Then we obtain a complete bipartite graph H=Kn+1,n with partite sets V1′={v1[i]:i∈[0,n-1]}∪{u} and V2′={v2[i]:i∈[0,n-1]}. Let H1(V,V2′)=Kn,n be a balanced complete bipartite graph with vertex setsV=V1′∖{u}={v1[i]:i∈[0,n-1]} and V2′={v2[i]:i∈[0,n-1]}. Let H2=Kn,1 be a complete bipartite graph with partite sets V2′={v2[i]:i∈[0,n-1]} and {u}. In fact, H2=Kn,1 is a star Sn+1 with the center u. Thus, H=H1∪H2. Since the edge set of H1(V,V2′)=Kn,n can be partitioned into n pairwise disjoint perfect matchings M0,M1,…,Mn-1 such that Mj is exactly the set of edges of bipartite difference j in Kn,n for j∈[0,n-1] and n is odd, the edge set of H=Kn+1,n can be partitioned into n pairwise disjoint edge sets M0′,M1′,…,Mn-1′ such that Mj′=Mj∪{uv2[2j]}(j∈[0,n-1]) which consists of a 2-path uv2[2j]v1[j] and n-1 isolated edges v1[i]v2[i+j](i∈[0,j-1]∪[j+1,n-1]), where 2j and i+j are taken modulo n.
Thus, each edgev1[i]v2[i+j](i∈[0,j-1]∪[j+1,n-1]) in Mj′ corresponds to a subgraph isomorphic to K4,2 and the 2-path uv2[2j]v1[j] corresponds to a subgraph isomorphic to K5,2 with partition (V1j∪{u},V2(2j)) in K4n+1,2n. Let
(4)V2(2j)={v2[2j]0,v2[2j]1},V1j={v1[j]0,v1[j]1,v1[j]2,v1[j]3},
where the indices 2j are taken modulo n.
After taking away the two edgesv1[j]0v2[2j]1,v1[j]1v2[2j]3 from each K5,2 to which the 2-path uv2[2j]v1[j] corresponds, each Mj′ corresponds to two linear 2-forests of K4n+1,2n by Lemma 5. The edges that we take away form one linear 2-forest. Hence la2(K4n+1,2n)≤2n+1 by Lemma 4. Since la2(K4n+1,2n)≥2n+1 by Lemma 3, we obtain la2(K4n+1,2n)=2n+1.


## 3. The Linear 4-Arboricity of Complete Bipartite GraphKm,n

Lemma 11.
One hasla4(K6,4)=3.Proof.
By Lemma3, la4(K6,4)≥3. In the following, K6,4 can be partitioned into three linear 4-forests: let K6,4=(V1,V2), where V1={vi:i∈[1,6]} and V2={uj:j∈[1,4]}. Clearly, K6,4 can be decomposed into three linear 4-forests {v1u1v2u2v3,v4u3v5u4v6}, {v2u3v1u4v3,v4u1v6u2v5}, and {v1u2v4u4v2,v5u1v3u3v6} (see Figure 1).
Thusla4(K6,4)=3.Figure 1
The decomposition of linear 4-forests ofk6,4.Lemma 12.
l
a
4
(
K
6,5
)
=
4.Proof.
By Lemma3, la4(K6,5)≥4. In the following, we partition the edge set of K6,5 into four linear 4-forests: let K6,5=(V1,V2), where V1={vi:i∈[1,6]} and V2={uj:j∈[1,5]}. Clearly, K6,5 can be decomposed into four linear 4-forests {v1u1v2u2,v3u3v4u4,v5u5v6}, {v1u5v2,u1v3u2v4,u3v5u4v6}, {v1u3v2u4,v3u5v4,u1v5u2v6}, and {u2v1u4v3,v4u1v6u3} (see Figure 2).
Thusla4(K6,5)=4.Figure 2
The decomposition of linear 4-forests ofK6,5.Lemma 13.
l
a
4
(
K
7,4
)
=
4.Proof.
By Lemma3, la4(K7,4)≥4. In the following, we partition the edge set of K7,4 into four linear 4-forests: let K7,4=(V1,V2), where V1={vi:i∈[1,7]} and V2={uj:j∈[1,4]}. K7,4 can be decomposed into four linear 4-forests {v1u1v2,v3u2v4,v5u3v6u4v7}, {v1u4v2,v3u1v4u3v7,v5u2v6}, {v1u3v2,v3u4v4,v6u1v7u2}, and {v1u2v2,u1v5u4,v3u3} (see Figure 3).
Thusla4(K7,4)=4.Figure 3
The decomposition of linear 4-forests ofK7,4.In the following, we mainly consider the complete bipartite graphsK6n,4n, K6n+1,4n, and K6n,4n+1.Theorem 14.
One hasla4(K6n,4n)=3n.Proof.
LetG(V1,V2)=K6n,4n be a complete bipartite graph with partite sets V1 and V2, where |V1|=6n and |V2|=4n. Next, we partition V1 and V2 into n vertex sets V1i and V2i, respectively, such that |V1i|=6 and |V2i|=4 for i∈[0,n-1].
For eachV1i(i∈[0,n-1]), we identify 6 vertices in V1i and denote a new vertex by v1[i]. For each V2i, we identify 4 vertices in V2i and denote a new vertex by v2[i]. Then we obtain a balanced complete bipartite graph H=Kn,n with vertex sets  V1′={v1[i]:i∈[0,n-1]} and V2′={v2[i]:i∈[0,n-1]}. The edge set of Kn,n can be partitioned into n pairwise disjoint perfect matchings M0,M1,…,Mn-1 such that Mj is exactly the set of edges of bipartite difference j in Kn,n for j∈[0,n-1]. Every edge in Mj corresponds to a subgraph of K6n,4n isomorphic to K6,4. Since la4(K6,4)=3 by Lemma 11, each Mj corresponds to three linear 4-forests in K6n,4n. Thus la4(K6n,4n)≤3n by Lemma 11. Applying Lemma 3, we have
(5)la4(K6n,4n)≥⌈6n·4n⌊4·(6n+4n)/5⌋⌉=3n.
Hencela4(K6n,4n)=3n.Corollary 15.
Considerla4(K6n,4n-1)=la4(K6n-1,4n)=3n.Proof.
The results can be obtained by Lemma3 and Theorem 14 immediately.Theorem 16.
l
a
4
(
K
4
n
+
1,6
n
)
=
3
n
+
1, where n is odd.Proof.
LetG(V1,V2)=K4n+1,6n be a complete bipartite graph with partite sets V1 and V2, where |V1|=4n+1 and |V2|=6n. Next, we partition V1 into n+1 vertex sets V1i(i∈[0,n]) and partition V2 into n vertex sets V2j, respectively, such that |V1j|=4, |V2j|=6 for j∈[0,n-1], and |V1n|=|{u}|=1.
For eachV1i(i∈[0,n-1]), we identify 4 vertices in V1i and denote a new vertex by v1[i]. For each V2i(i∈[0,n-1]), we identify 6 vertices in V2i and denote a new vertex by v2[i]. Then we obtain a complete bipartite graph H=Kn+1,n with partite sets V1′={v1[i]:i∈[0,n-1]}∪{u} and V2′={v2[i]:i∈[0,n-1]}. Let H1(V,V2′)=Kn,n be a balanced complete bipartite graph with partite sets V=V1′∖{u}={v1[i]:i∈[0,n-1]} and V2′. Let H2=Kn,1 be a complete bipartite graph with vertex sets  V2′ and {u}. In fact, H2=Kn,1 is a star Sn+1 with the center u. Thus, H=H1∪H2. Since the edge set of H1(V,V2′)=Kn,n can be partitioned into n pairwise disjoint perfect matchings M0,M1,…,Mn-1 such that Mj is exactly the set of edges of bipartite difference j in Kn,n for j∈[0,n-1] and n is odd, the edge set of H=Kn+1,n can be partitioned into n pairwise disjoint edge sets M0′,M1′,…,Mn-1′ such that Mj′=Mj∪{uv2[2j]}(j∈[0,n-1]) which consists of a 2-path uv2[2j]v1[j] and n-1 isolated edges v1[i]v2[i+j](i∈[0,j-1]∪[j+1,n-1]), where 2j,i+j are taken modulo n.
Thus, each edgev1[i]v2[i+j](i∈[0,j-1]∪[j+1,n-1]) in Mj′ corresponds to a subgraph isomorphic to K6,4 and the 2-path uv2[2j]v1[j] corresponds to a subgraph isomorphic to K6,5 with partition (V2(2j),V1j∪{u}) in K6n,4n+1, where 2j is taken modulo n. Let
(6)V1j={v1[j]0,v1[j]1,v1[j]2,v1[j]3},V2(2j)={v2[2j]0,v2[2j]1,…,v2[2j]5},
where the indices 2j are taken modulo n.
After taking away the six edgesv2[2j]0v1[j]1,v2[2j]0v1[j]3,v2[2j]2v1[j]3,v2[2j]3v1[j]0,v2[2j]5v1[j]0, and v2[2j]5v1[j]2 from each K6,5 to which the 2-path uv2[2j]v1[j] corresponds, each Mj′ corresponds to three linear 4-forests of K6n,4n+1 by Lemma 12. The edges that we take away form one linear 4-forest (see Figure 2). Hence la4(K6n,4n+1)≤3n+1 by Lemma 11. Since
(7)la4(K6n,4n+1)≥⌈6n(4n+1)⌊4·(6n+4n+1)/5⌋⌉=3n+1
by Lemma 3, we have la4(K6n,4n+1)=3n+1.Corollary 17.
l
a
4
(
K
6
n
-
1,4
n
+
1
)
=
3
n
+
1, where n is odd.Proof.
The results can be obtained by Lemma3 and Theorem 16 immediately.Theorem 18.
l
a
4
(
K
6
n
+
1,4
n
)
=
3
n
+
1, where n is odd.Proof.
The proof is similar to Theorem16. Let G(V1,V2)=K6n+1,4n be a complete bipartite graph with partite sets V1 and V2, where |V1|=6n+1 and |V2|=4n. Next, we partition V2 into n vertex subsets V2i(i∈[0,n-1]) and partition V1 into n+1 vertex subsets V1i(i∈[0,n]), respectively, such that |V2i|=4, |V1i|=6 for i∈[0,n-1], and |V1n|=|{u}|=1.
For eachV1i(i∈[0,n-1]), we identify 6 vertices in V1i and denote a new vertex by v1[i]. For each V2i(i∈[0,n-1]), we identify 4 vertices in V2i and denote a new vertex by v2[i]. Then we obtain a complete bipartite graph H=Kn+1,n with partite sets V1′={v1[i]:i∈[0,n-1]}∪{u} and V2′={v2[i]:i∈[0,n-1]}. Let H1(V,V2′)=Kn,n be a balanced complete bipartite graph with vertex sets  V=V1′∖{u}={v1[i]:i∈[0,n-1]} and V2′={v2[i]:i∈[0,n-1]}. Let H2=Kn,1 be a complete bipartite graph with partite sets V2′={v2[i]:i∈[0,n-1]} and {u}. In fact, H2=Kn,1 is a star Sn+1 with the center u. Thus, H=H1∪H2. Since the edge set of H1(V,V2′)=Kn,n can be partitioned into n pairwise disjoint perfect matchings M0,M1,…,Mn-1 such that Mj is exactly the set of edges of bipartite difference j in Kn,n for j∈[0,n-1] and n is odd, the edge set of H=Kn+1,n can be partitioned into n pairwise disjoint edge sets M0′,M1′,…,Mn-1′ such that Mj′=Mj∪{uv2[2j]}(j∈[0,n-1]) which consists of a 2-path uv2[2j]v1[j] and n-1 isolated edges v1[i]v2[i+j](i∈[0,j-1]∪[j+1,n-1]), where 2j,i+j are taken modulo n.
Thus, each edgev1[i]v2[i+j](i∈[0,j-1]∪[j+1,n-1]) in Mj′ corresponds to a subgraph isomorphic to K6,4 and the 2-path uv2[2j]v1[j] corresponds to a subgraph isomorphic to K7,4 with partition (V1j∪{u},V2(2j)) in K6n+1,4n, where 2j is taken modulo n. Let
(8)V2(2j)={v2[2j]0,v2[2j]1,v2[2j]2,v2[2j]3},V1j={v1[j]0,v1[j]1,…,v1[j]5},
where the indices 2j are taken modulo n.
After taking away five edgesv1[j]0v2[2j]1, v1[j]1v2[2j]1, v1[j]2v2[2j]2, v1[j]4v2[2j]0, and v1[j]4v2[2j]3 from each K7,4 to which the 2-path uv2[2j]v1[j] corresponds, where the indices 2j are taken modulo n, each Mj′ corresponds to three linear 4-forests of K6n+1,4n by Lemma 13. The edges that we take away form one linear 4-forest (see Figure 3). Hence la4(K6n+1,4n)≤3n+1 by Lemma 11. Since
(9)la4(K6n+1,4n)≥⌈(6n+1)4n⌊4·(6n+1+4n)/5⌋⌉=3n+1
by Lemma 3, we obtain la4(K6n+1,4n)=3n+1.Corollary 19.
l
a
4
(
K
6
n
+
1,4
n
-
1
)
=
3
n
+
1, where n is odd.Proof.
The results can be obtained by Lemma3 and Theorem 18 immediately.



---

*Source: 501701-2013-12-30.xml*