Geodesic
Decompositions of Cubic Traceable Graphs
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 35-49.

Voir la notice de l'article provenant de la source Library of Science

A traceable graph is a graph with a Hamilton path. The 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular graph and a matching. We prove the conjecture for cubic traceable graphs.
Keywords: decomposition, cubic traceable graph, spanning tree, matching, 2-regular graph 
@article{DMGT_2020_40_1_a2,
     author = {Liu, Wenzhong and Li, Panpan},
     title = {Decompositions of {Cubic} {Traceable} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {35--49},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a2/}
}
TY  - JOUR
AU  - Liu, Wenzhong
AU  - Li, Panpan
TI  - Decompositions of Cubic Traceable Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 35
EP  - 49
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a2/
LA  - en
ID  - DMGT_2020_40_1_a2
ER  - 
%0 Journal Article
%A Liu, Wenzhong
%A Li, Panpan
%T Decompositions of Cubic Traceable Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 35-49
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a2/
%G en
%F DMGT_2020_40_1_a2
Liu, Wenzhong; Li, Panpan. Decompositions of Cubic Traceable Graphs. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 35-49. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a2/

[1] S. Akbari, T.R. Jensen and M. Siggers, Decompositions of graphs into trees, forests, and regular subgraphs, Discrete Math. 338 (2015) 1322–1327. doi:10.1016/j.disc.2015.02.021

[2] M.O. Albertson, D.M. Berman, J.P. Hutchinson and C. Thomassen, Graphs with homeomorphically irreducible spanning trees, J. Graph Theory 14 (1990) 247–258. doi:10.1002/jgt.3190140212

[3] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, New York, 2008).

[4] P.J. Cameron, Research problems from the BCC 22, Discrete Math. 311 (2011) 1074–1083. doi:10.1016/j.disc.2011.02.024

[5] G.T. Chen, H. Ren and S.L. Shan, Homeomorphically irreducible spanning trees in locally connected graphs, Combin. Probab. Comput. 21 (2012) 107–111. doi:10.1017/S0963548311000526

[6] G.T. Chen and S.L. Shan, Homeomorphically irreducible spanning trees, J. Combin. Theory Ser. B 103 (2013) 409–414. doi:10.1016/j.jctb.2013.04.001

[7] J. Diemunsch, M. Furuya, M. Sharifzadeh, S. Tsuchiya, D. Wang, J. Wise and E. Yeager, A characterization of P 5 -free graphs with a homeomorphically irreducible spanning tree, Discrete Appl. Math. 185 (2015) 71–78. doi:10.1016/j.dam.2014.12.023

[8] R.J. Douglas, NP-completeness and degree restricted spanning trees, Discrete Math. 105 (1992) 41–47. doi:10.1016/0012-365X(92)90130-8

[9] G.H. Fan and A. Raspaud, Fulkerson’s conjecture and circuit covers, J. Combin. Theory Ser. B 61 (1994) 133–138. doi:10.1006/jctb.1994.1039

[10] A. Hoffmann-Ostenhof, Nowhere-Zero Flows and Structures in Cubic Graphs, Ph.D. Dissertation (University of Vienna, 2011).

[11] A. Hoffmann-Ostenhof, A survey on the 3-decomposition conjecture (2016), manuscript.

[12] A. Hoffmann-Ostenhof, T. Kaiser and K. Ozeki, Decomposing planar cubic graphs, J. Graph Theory 88 (2018) 631–640. doi:10.1002/jgt.22234

[13] A. Kostochka, Spanning trees in 3-regular graphs, in: REGS in Combinatorics (University of Illinois at Urbana-Champaign, 2009).

[14] J. Malkevitch, Spanning trees in polytopal graphs, Ann. New York Acad. Sci. 319 (1979) 362–367. doi:10.1111/j.1749-6632.1979.tb32810.x

[15] K. Ozeki and D. Ye, Decomposing plane cubic graphs, European J. Combin. 52 (2016) 40–46. doi:10.1016/j.ejc.2015.08.005

[16] J. Petersen, Die Theorie der regulären graphen, Acta Math. 15 (1891) 193–220. doi:10.1007/BF02392606

[17] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Metody Diskret. Anal. 3 (1964) 25–30, in Russian.

[18] D.B. West, Introduction to Graph Theory (Prentice-Hall, 2001).

[19] D. Ye, (2016), personal communication.