Decomposing graphs into paths of fixed length. (English) Zbl 1299.05270
The paper addresses the following conjecture of Barát and Thomassen: For each tree \(T\) there is a natural number \(k = k(T)\) such that any graph \(G\) that is \(k\)-edge connected with \(| E(T)| \) dividing \(| E(G)| \) can be decomposed into edge disjoint copies of the tree \(T\). This conjecture is verified for any tree \(P\) that is a path of length \(p\) a power of \(2\). The proof involves vertex colorings and multi-edge-colorings of a multi-graph \(G\) with edge-connectivity at least \(\alpha(p, m)\), where each edge has at most \(m\) colors and no vertex sees a color more than once.
Reviewer: Ralph Faudree (Memphis)
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C05 | Trees |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C38 | Paths and cycles |
| 05C40 | Connectivity |
References:
| [1] | J. Bang-Jensen, S. Thomassé and A. Yeo: Small degree out-branchings, J. Graph Theory42 (2003), 297-307. · Zbl 1018.05041 · doi:10.1002/jgt.10092 |
| [2] | J. Barát and C. Thomassen: Claw-decompositions and Tutte-orientations, J. Graph Theory52 (2006), 135-146. · Zbl 1117.05088 · doi:10.1002/jgt.20149 |
| [3] | J. A. Bondy: Double covers of graphs, J. Graph Theory14 (1990), 259-273. · Zbl 0745.05038 · doi:10.1002/jgt.3190140213 |
| [4] | J. A. Bondy and U. S. R. Murty: Graph Theory with Applications, The MacMillan Press Ltd. (1976). · Zbl 1226.05083 |
| [5] | A. Czumaj and W. B. Strothmann: Bounded degree spanning trees, In: Algorithms-ESA 97 (Graz), Springer lecture notes in computer science1284 (1997), 104-117. · Zbl 1477.68215 · doi:10.1007/3-540-63397-9_9 |
| [6] | R. Diestel: Graph Theory, Springer Verlag (1997) and 2nd edition (2000). · Zbl 0873.05001 |
| [7] | D. Dor and M. Tarsi: Graph decomposition is NP-complete: a complete proof of Holyer’s conjecture, SIAM J. Comput.26 (1997), 1166-1187. · Zbl 0884.05071 · doi:10.1137/S0097539792229507 |
| [8] | J. Edmonds: Minimum partition of a matroid into independent subsets, J. Res. Nat. Bur. Standards Sect. B69B (1965), 67-72. · Zbl 0192.09101 · doi:10.6028/jres.069B.004 |
| [9] | K. Heinrich, J. Liu and M. Yu: P4-decompositions of regular graphs, J. Graph Theory31 (1999), 135-143. · Zbl 0927.05067 · doi:10.1002/(SICI)1097-0118(199906)31:2<135::AID-JGT6>3.0.CO;2-I |
| [10] | Jaeger, F.; Beineke, L. W (ed.), Nowhere-zero flow problems, 71-95 (1988) · Zbl 0658.05034 |
| [11] | M. Jünger, G. Reinelt and W. Pulleyblank: On partitioning the edges of graphs into connected subgraphs, J. Graph Theory9 (1985), 539-549. · Zbl 0665.05040 · doi:10.1002/jgt.3190090416 |
| [12] | D. Kühn and D. Osthus: Every graph of sufficiently large average degree contains a C4-free subgraph of large average degree, Combinatorica24 (2004), 155-162. · Zbl 1047.05022 · doi:10.1007/s00493-004-0010-2 |
| [13] | L. Lovász: On some connectivity properties of eulerian graphs, Acta Math. Acad. Sci. Hung.28 (1976), 129-138. · Zbl 0337.05124 · doi:10.1007/BF01902503 |
| [14] | W. Mader: A reduction method for edge-connectivity in graphs, Ann. Discrete Math.3 (1978), 145-164. · Zbl 0389.05042 · doi:10.1016/S0167-5060(08)70504-1 |
| [15] | B. Mohar and C. Thomassen: Graphs on Surfaces, Johns Hopkins University Press (2001). · Zbl 0979.05002 |
| [16] | C. St. J. A. Nash-Williams: Edge-disjoint spanning trees of finite graphs, J. London Math. Soc.36 (1961), 445-450. · Zbl 0102.38805 · doi:10.1112/jlms/s1-36.1.445 |
| [17] | C. Thomassen: Graph decomposition with applications to subdivisions and path systems modulo k, J. Graph Theory7 (1983), 261-271. · Zbl 0515.05052 · doi:10.1002/jgt.3190070215 |
| [18] | C. Thomassen: Girth in graphs, J. Combinatorial Theory, Ser. B35 (1983), 129-141. · Zbl 0537.05034 · doi:10.1016/0095-8956(83)90067-9 |
| [19] | C. Thomassen: Decompositions of highly connected graphs into paths of length 4, Abh. Math. Seminar Hamburg78 (2008), 17-26. · Zbl 1181.05057 · doi:10.1007/s12188-008-0002-z |
| [20] | C. Thomassen: Decompositions of highly connected graphs into paths of length 3, J. Graph Theory58 (2008), 286-292. · Zbl 1214.05134 · doi:10.1002/jgt.20311 |
| [21] | C. Thomassen: The weak 3-flow conjecture and the weak circular flow conjecture, J. Combinatorial Theory Ser.B102 (2012), 521-529. · Zbl 1239.05083 · doi:10.1016/j.jctb.2011.09.003 |
| [22] | W. T. Tutte: On the problem of decomposing a graph into n connected factors, J. London Math. Soc.36 (1961), 221-230. · Zbl 0096.38001 · doi:10.1112/jlms/s1-36.1.221 |
| [23] | D. J. A. Welsh: Matroid Theory, Academic Press (1976). · Zbl 0343.05002 |
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.
