Decomposition of Graphs into Paths
Resumo
We study the Decomposition Conjecture posed by Barát and Thomassen (2006), which states that, for each tree T, there exists a natural number kT such that, if G is a kT-edge-connected graph and |E(T)| divides |E(G)|, then G admits a partition of its edge set into copies of T. In a series of papers, Thomassen has verified this conjecture for stars, some bistars, paths of length 3, and paths whose length is a power of 2. In this paper we prove this conjecture for paths of any given length. Our technique is then used to prove weakenings of a conjecture of Kouider and Lonc (1999), and a conjecture of Favaron, Genest and Kouider (2010), both for path decomposition of regular graphs.
Referências
Barát, J. and Gerbner, D. (2014). Edge-decompositions of graphs into copies of a tree with four edges. Electron. J. Combin., 21(1):Research Paper 55 pp. (electronic).
Barát, J. and Thomassen, C. (2006). Claw-decompositions and Tutte-orientations. J. Graph Theory, 52(2):135–146.
Bensmail, J., Harutyunyan, A., Le, T., Merker, M., and Thomassé, S. (2017). A proof of the Barát-Thomassen conjecture. J. Comb. Theory, Ser. B, 124:39–55.
Bensmail, J., Harutyunyan, A., Le, T.-N., and Thomassé, S. (2015). Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture. ArXiv e-prints.
Botler, F. (2016). Decomposição de Grafos em Caminhos. PhD thesis, Instituto de Matemática e Estatística – Universidade de São Paulo.
Botler, F., Mota, G., Oshiro, M., and Wakabayashi, Y. (2015a). Decompositions of highly connected graphs into paths of any given length. Electronic Notes in Discrete Mathematics, 49:795 – 802.
Botler, F., Mota, G., Oshiro, M., and Wakabayashi, Y. (2015b). Path decompositions of regular graphs with prescribed girth. Electronic Notes in Discrete Mathematics, 49:629 – 636.
Botler, F., Mota, G. O., Oshiro, M. T. I., and Wakabayashi, Y. (2016). Decomposing highly connected graphs into paths of length five. Discrete Appl. Math., to appear.
Botler, F., Mota, G. O., Oshiro, M. T. I., and Wakabayashi, Y. (2017a). Decomposing highly edge-connected graphs into paths of any given length. J. Combin. Theory Ser. B, 122:508–542.
Botler, F., Mota, G. O., Oshiro, M. T. I., and Wakabayashi, Y. (2017b). Decomposing regular graphs with prescribed girth into paths. European Journal of Combinatorics, to appear.
Botler, F., Mota, G. O., and Wakabayashi, Y. (2015c). Decompositions of triangle-free 5-regular graphs into paths of length five. Discrete Math., 338(11):1845–1855.
Botler, F. and Talon, A. (2017). Decomposing 8-regular graphs into paths of length 4. Discrete Mathematics, 340(9):2275 – 2285.
Diestel, R. (2010). Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Heidelberg, fourth edition.
Dor, D. and Tarsi, M. (1997). Graph decomposition is NP-complete: a complete proof of Holyer’s conjecture. SIAM J. Comput., 26(4):1166–1187.
Edwards, M. and Howard, L. (2006). A survey of graceful trees. Atl. Electron. J. Math., 1(1):5–30.
Favaron, O., Genest, F., and Kouider, M. (2010). Regular path decompositions of odd regular graphs. J. Graph Theory, 63(2):114–128.
Häggkvist, R. (1989). Decompositions of complete bipartite graphs. In Surveys in combinatorics, 1989 (Norwich, 1989), volume 141 of London Math. Soc. Lecture Note Ser., pages 115–147. Cambridge Univ. Press, Cambridge.
Heinrich, K., Liu, J., and Yu, M. (1999). P4-decompositions of regular graphs. J. Graph Theory, 31(2):135–143.
Jaeger, F. (1988). Nowhere-zero flow problems. In Selected topics in graph theory, 3, pages 71–95. Academic Press, San Diego, CA.
Kotzig, A. (1957). Aus der Theorie der endlichen regulären Graphen dritten und vierten Grades. Časopis Pěst. Mat., 82:76–92.
Kouider, M. and Lonc, Z. (1999). Path decompositions and perfect path double covers. Australas. J. Combin., 19:261–274.
Lovász, L. (1968). On covering of graphs. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pages 231–236. Academic Press, New York.
Lovász, L. M., Thomassen, C., Wu, Y., and Zhang, C.-Q. (2013). Nowhere-zero 3-flows and modulo k-orientations. J. Combin. Theory Ser. B, 103(5):587–598.
Merker, M. (2017). Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree. J. Comb. Theory, Ser. B, 122:91–108.
Petersen, J. (1891). Die Theorie der regulären graphs. Acta Math., 15(1):193–220.
Ringel, G. (1964). Problem n.25. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague.
Rosa, A. (1967). On certain valuations of the vertices of a graph. In Theory of Graphs (Internat. Sympos., Rome, 1966), pages 349–355. Gordon and Breach, New York.
Thomassen, C. (2008a). Decompositions of highly connected graphs into paths of length 3. J. Graph Theory, 58(4):286–292.
Thomassen, C. (2008b). Edge-decompositions of highly connected graphs into paths. Abh. Math. Semin. Univ. Hambg., 78(1):17–26.
Thomassen, C. (2013a). Decomposing a graph into bistars. J. Combin. Theory Ser. B, 103(4):504–508.
Thomassen, C. (2013b). Decomposing graphs into paths of fixed length. Combinatorica, 33(1):97–123.
Barát, J. and Thomassen, C. (2006). Claw-decompositions and Tutte-orientations. J. Graph Theory, 52(2):135–146.
Bensmail, J., Harutyunyan, A., Le, T., Merker, M., and Thomassé, S. (2017). A proof of the Barát-Thomassen conjecture. J. Comb. Theory, Ser. B, 124:39–55.
Bensmail, J., Harutyunyan, A., Le, T.-N., and Thomassé, S. (2015). Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture. ArXiv e-prints.
Botler, F. (2016). Decomposição de Grafos em Caminhos. PhD thesis, Instituto de Matemática e Estatística – Universidade de São Paulo.
Botler, F., Mota, G., Oshiro, M., and Wakabayashi, Y. (2015a). Decompositions of highly connected graphs into paths of any given length. Electronic Notes in Discrete Mathematics, 49:795 – 802.
Botler, F., Mota, G., Oshiro, M., and Wakabayashi, Y. (2015b). Path decompositions of regular graphs with prescribed girth. Electronic Notes in Discrete Mathematics, 49:629 – 636.
Botler, F., Mota, G. O., Oshiro, M. T. I., and Wakabayashi, Y. (2016). Decomposing highly connected graphs into paths of length five. Discrete Appl. Math., to appear.
Botler, F., Mota, G. O., Oshiro, M. T. I., and Wakabayashi, Y. (2017a). Decomposing highly edge-connected graphs into paths of any given length. J. Combin. Theory Ser. B, 122:508–542.
Botler, F., Mota, G. O., Oshiro, M. T. I., and Wakabayashi, Y. (2017b). Decomposing regular graphs with prescribed girth into paths. European Journal of Combinatorics, to appear.
Botler, F., Mota, G. O., and Wakabayashi, Y. (2015c). Decompositions of triangle-free 5-regular graphs into paths of length five. Discrete Math., 338(11):1845–1855.
Botler, F. and Talon, A. (2017). Decomposing 8-regular graphs into paths of length 4. Discrete Mathematics, 340(9):2275 – 2285.
Diestel, R. (2010). Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Heidelberg, fourth edition.
Dor, D. and Tarsi, M. (1997). Graph decomposition is NP-complete: a complete proof of Holyer’s conjecture. SIAM J. Comput., 26(4):1166–1187.
Edwards, M. and Howard, L. (2006). A survey of graceful trees. Atl. Electron. J. Math., 1(1):5–30.
Favaron, O., Genest, F., and Kouider, M. (2010). Regular path decompositions of odd regular graphs. J. Graph Theory, 63(2):114–128.
Häggkvist, R. (1989). Decompositions of complete bipartite graphs. In Surveys in combinatorics, 1989 (Norwich, 1989), volume 141 of London Math. Soc. Lecture Note Ser., pages 115–147. Cambridge Univ. Press, Cambridge.
Heinrich, K., Liu, J., and Yu, M. (1999). P4-decompositions of regular graphs. J. Graph Theory, 31(2):135–143.
Jaeger, F. (1988). Nowhere-zero flow problems. In Selected topics in graph theory, 3, pages 71–95. Academic Press, San Diego, CA.
Kotzig, A. (1957). Aus der Theorie der endlichen regulären Graphen dritten und vierten Grades. Časopis Pěst. Mat., 82:76–92.
Kouider, M. and Lonc, Z. (1999). Path decompositions and perfect path double covers. Australas. J. Combin., 19:261–274.
Lovász, L. (1968). On covering of graphs. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pages 231–236. Academic Press, New York.
Lovász, L. M., Thomassen, C., Wu, Y., and Zhang, C.-Q. (2013). Nowhere-zero 3-flows and modulo k-orientations. J. Combin. Theory Ser. B, 103(5):587–598.
Merker, M. (2017). Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree. J. Comb. Theory, Ser. B, 122:91–108.
Petersen, J. (1891). Die Theorie der regulären graphs. Acta Math., 15(1):193–220.
Ringel, G. (1964). Problem n.25. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963). Publ. House Czechoslovak Acad. Sci., Prague.
Rosa, A. (1967). On certain valuations of the vertices of a graph. In Theory of Graphs (Internat. Sympos., Rome, 1966), pages 349–355. Gordon and Breach, New York.
Thomassen, C. (2008a). Decompositions of highly connected graphs into paths of length 3. J. Graph Theory, 58(4):286–292.
Thomassen, C. (2008b). Edge-decompositions of highly connected graphs into paths. Abh. Math. Semin. Univ. Hambg., 78(1):17–26.
Thomassen, C. (2013a). Decomposing a graph into bistars. J. Combin. Theory Ser. B, 103(4):504–508.
Thomassen, C. (2013b). Decomposing graphs into paths of fixed length. Combinatorica, 33(1):97–123.
Publicado
02/07/2017
Como Citar
BOTLER, Fábio; WAKABAYASHI, Yoshiko.
Decomposition of Graphs into Paths. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 30. , 2017, São Paulo.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 2343-2348.
ISSN 2763-8820.
DOI: https://doi.org/10.5753/ctd.2017.3454.
