An Improved Upper Bound on the Linear 2-arboricity of 1-planar Graphs
- PDF / 334,607 Bytes
- 17 Pages / 510.236 x 737.008 pts Page_size
- 65 Downloads / 213 Views
Acta Mathematica Sinica, English Series Springer-Verlag GmbH Germany & The Editorial Office of AMS 2020
An Improved Upper Bound on the Linear 2-arboricity of 1-planar Graphs Juan LIU Department of Mathematics, Zhejiang Normal University, Jinhua 321004, P. R. China E-mail : [email protected]
Yi Qiao WANG School of Management, Beijing University of Chinese Medicine, Beijing 100029, P. R. China E-mail : [email protected]
Ping WANG Department of Mathematics and Statistics, St. Francis Xavier University, Antigonish, Nova Scotia, Canada E-mail : [email protected]
Lu ZHANG Department of Mathematics, Zhejiang Normal University, Jinhua 321004, P. R. China E-mail : [email protected]
Wei Fan WANG1) Department of Mathematics, Zhejiang Normal University, Jinhua 321004, P. R. China E-mail : [email protected] Abstract The linear 2-arboricity la2 (G) of a graph G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose component trees are paths of length at most 2. In this + 7. This paper, we prove that if G is a 1-planar graph with maximum degree Δ, then la2 (G) ≤ Δ+1 2 + 14. We improves a known result of Liu et al. (2019) that every 1-planar graph G has la2 (G) ≤ Δ+1 2 + 2, which also observe that there exists a 7-regular 1-planar graph G such that la2 (G) = 6 = Δ+1 2 implies that our solution is within 6 from optimal. Keywords
1-planar graph, linear 2-arboricity, edge-partition, maximum degree
MR(2010) Subject Classification
1
05C15
Introduction
All graphs considered in this paper are finite simple graphs. For a graph G, we use V (G), E(G), δ(G), and Δ(G) to denote its vertex set, edge set, minimum degree, and maximum degree, respectively. An edge-partition of a graph G is a decomposition of G into subgraphs G1 , G2 , . . . , Gm such that E(G) = E(G1 ) ∪ E(G2 ) ∪ · · · ∪ E(Gm ) and E(Gi ) ∩ E(Gj ) = ∅ for i = j. A linear Received November 5, 2019, revised March 7, 2020, accepted June 5, 2020 1) Corresponding author
Liu J. et al.
2
k-forest is a graph whose components are paths of length at most k. The linear k-arboricity of G, denoted by lak (G), is the least integer m such that G can be edge-partitioned into m linear k-forests. Clearly, lak (G) ≥ lak+1 (G) for any k ≥ 1. For extremities, la1 (G) is the chromatic index χ (G) of G, and la∞ (G) is the linear arboricity la(G) of G. The linear k-arboricity of a graph was introduced by Habib and Proche [1]. Among other things, the following challenging problem was proposed in [1]: Conjecture 1.1
Let G be a graph with n vertices and k ≥ 2 be an integer. Then ⎧ nΔ(G) + 1 ⎪ ⎪ , if Δ(G) = n − 1; ⎪ kn ⎨ 2 k+1 lak (G) ≤ nΔ(G) ⎪ ⎪ ⎪ , if Δ(G) = n − 1. ⎩ kn 2 k+1
For some fixed values k, the linear k-arboricities of some special graphs such as cycles, trees, complete graphs, and complete bipartite graphs were determined in [4–6, 8]. Thomassen [12] showed that every subcubic graph G has la5 (G) ≤ 2, and la4 (G) ≤ 2 does not always hold for + 12; subcubic graphs. Lih et al. [9] proved that every planar graph G has la2 (G) ≤
Data Loading...
