×

An efficient case for computing minimum linear arboricity with small maximum degree. (English) Zbl 1420.90062

Summary: Graph coloring has interesting applications in optimization, calculation of Hessian matrix, network design and so on. In this paper, we consider an improper edge coloring which is one important coloring-linear arboricity. For a graph \(G\), a linear forest is a disjoint union of paths and cycles. The linear arboricity \(\mathrm{la}(G)\) is the minimum number of disjoint linear forests such that their union is exactly the edge set of \(G\). In this paper, we study a special case that \(G\) is a simple planar graph with two not adjacent cycles each with a chordal and length between 4 and 7. We show that in this special case, \(\mathrm{la}(G)=\lceil \frac{\Delta }{2}\rceil \) where \(\Delta \) is the maximum vertex degree of \(G\) and \(\Delta \ge 7\).

MSC:

90C27 Combinatorial optimization
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akiyama, J., Exoo, G., Harary, F.: Covering and packing in graphs III: cyclic and acyclic invariants. Math. Slovaca 30, 405-417 (1980) · Zbl 0458.05050
[2] Akiyama, J., Exoo, G., Harary, F.: Covering and packing in graphs IV: linear arboricity. Networks 11, 69-72 (1981) · Zbl 0479.05027 · doi:10.1002/net.3230110108
[3] Alon, N.: The linear arboricity of graphs. Isr. J. Math. 62, 311-325 (1988) · Zbl 0673.05019 · doi:10.1007/BF02783300
[4] Alon, N., Teague, V.J., wormald, N.C.: Linear arboricity and linear \[k\] k-arboricity of regular graphs. Graphs Comb. 17, 11-16 (2001) · Zbl 0982.05079 · doi:10.1007/PL00007233
[5] Angelini, P., Frati, F.: Acyclically 3-colorable planar graphs. J Comb. Optim. 24, 116-130 (2012) · Zbl 1258.05025 · doi:10.1007/s10878-011-9385-3
[6] Bessy, S., Havet, F.: Enumerating the edge-colourings and total colourings of a regular graph. J Comb. Optim. 25, 523-535 (2013) · Zbl 1271.05050 · doi:10.1007/s10878-011-9448-5
[7] Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. North-Holland, New York (1976) · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2
[8] Cygan, M., Hou, J.F., Kowalik, L., Luzar, B., Wu, J.L.: A planar linear arboricity conjecture. J. Graph Theory 69, 403-425 (2012) · Zbl 1242.05064 · doi:10.1002/jgt.20592
[9] Du, H.W., Jia, X.H., Li, D.Y., Wu, W.L.: Coloring of double disk graphs. J. Global Optim. 28, 115-119 (2004) · Zbl 1034.05021 · doi:10.1023/B:JOGO.0000006750.85332.0f
[10] Li, X.W., Mak-Hau, V., Zhou, S.M.: The \[L(2,1)\] L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups. J Comb. Optim. 25, 716-736 (2013) · Zbl 1273.90227 · doi:10.1007/s10878-012-9525-4
[11] Li, Y., Hu, X.: The linear 2-arboricity of sparse graphs. Discrete Math. Algorithms Appl. 9, 1750047 (2017) · Zbl 1377.05099 · doi:10.1142/S1793830917500471
[12] Orponen, P., Russo, D.A.: Uwe Schōning: optimal approximations and polynomially levelable sets. SIAM J. Comput. 15(2), 399-408 (1986) · Zbl 0644.68054 · doi:10.1137/0215027
[13] Péoche, B.: Complexity of the linear arboricity of a graph. RAIRO Rech. Oper. 16, 125-129 (1982) · Zbl 0492.05025 · doi:10.1051/ro/1982160201251
[14] Wang, H.J., Liu, B., Gu, Y., Zhang, X., Wu, W.L., Gao, H.W.: Total coloring of planar graphs without adjacent short cycles. J. Comb. Optim. 33, 265-274 (2017) · Zbl 1367.05081 · doi:10.1007/s10878-015-9954-y
[15] Wang, H.J., Wu, J.L., Liu, B., Chen, H.Y.: On the linear arboricity of graphs embeddable in surfaces. Inf. Process. Lett. 114, 475-479 (2014) · Zbl 1294.05129 · doi:10.1016/j.ipl.2014.03.013
[16] Wang, H.J., Wu, L.D., Wu, W.L., Pardalos, P.M., Wu, J.L.: Minimum total coloring of planar graph. J. Global Optim. 60, 777-791 (2014) · Zbl 1308.90193 · doi:10.1007/s10898-013-0138-y
[17] Wang, H.J., Wu, L.D., Wu, W.L., Wu, J.L.: Minimum number of disjoint linear forests covering a planar graph. J. Comb. Optim. 28, 274-287 (2014) · Zbl 1328.90153 · doi:10.1007/s10878-013-9680-2
[18] Wang, H.J., Wu, L.D., Zhang, X., Wu, W.L., Liu, B.: A note on the minimum number of choosability of planar graphs. J. Comb. Optim. 31, 1013-1022 (2016) · Zbl 1344.90065 · doi:10.1007/s10878-014-9805-2
[19] Wu, J.L.: On the linear arboricity of planar graphs. J. Graph Theory 31, 129-134 (1999) · Zbl 0933.05056 · doi:10.1002/(SICI)1097-0118(199906)31:2<129::AID-JGT5>3.0.CO;2-A
[20] Wu, J.L., Wu, Y.W.: The linear arboricity of planar graphs of maximum degree seven are four. J. Graph Theory 58, 210-220 (2008) · Zbl 1158.05023 · doi:10.1002/jgt.20305
[21] Wu, J.L.: Some path decompositions of Halin graphs. J. Shandong Min. Inst. 15, 219-222 (1996)
[22] Wu, J.L.: The linear arboricity of series-parallel graphs. Graphs Combin. 16, 367-372 (2000) · Zbl 0963.05073 · doi:10.1007/s373-000-8299-9
[23] Wu, J.L., Hou, J.F., Sun, X.Y.: A note on the linear arboricity of planar graphs without 4-cycles. ISORA’09, pp. 174-178 (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.