Geodesic
Ascending Subgraph Decompositions of Oriented Graphs that Factor into Triangles
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 811-822.

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

In 1987, Alavi, Boals, Chartrand, Erdős, and Oellermann conjectured that all graphs have an ascending subgraph decomposition (ASD). In a previous paper, Wagner showed that all oriented complete balanced tripartite graphs have an ASD. In this paper, we will show that all orientations of an oriented graph that can be factored into triangles with a large portion of the triangles being transitive have an ASD. We will also use the result to obtain an ASD for any orientation of complete multipartite graphs with 3n partite classes each containing 2 vertices (a K(2 : 3n)) or 4 vertices (a K(4 : 3n)).
Keywords: ascending subgraph decomposition, graph factorization, Oberwolfach problem 
@article{DMGT_2022_42_3_a8,
     author = {Austin, Andrea D. and Wagner, Brian C.},
     title = {Ascending {Subgraph} {Decompositions} of {Oriented} {Graphs} that {Factor} into {Triangles}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {811--822},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a8/}
}
TY  - JOUR
AU  - Austin, Andrea D.
AU  - Wagner, Brian C.
TI  - Ascending Subgraph Decompositions of Oriented Graphs that Factor into Triangles
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 811
EP  - 822
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a8/
LA  - en
ID  - DMGT_2022_42_3_a8
ER  - 
%0 Journal Article
%A Austin, Andrea D.
%A Wagner, Brian C.
%T Ascending Subgraph Decompositions of Oriented Graphs that Factor into Triangles
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 811-822
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a8/
%G en
%F DMGT_2022_42_3_a8
Austin, Andrea D.; Wagner, Brian C. Ascending Subgraph Decompositions of Oriented Graphs that Factor into Triangles. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 811-822. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a8/

[1] Y. Alavi, A.J. Boals, G. Chartrand, P. Erdős and O. Oellermann, The ascending subgraph decomposition problem, Congr. Numer. 58 (1987) 7–14.

[2] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs, 4th Ed. (Chapman & Hall/CRC, Boca Raton, 2005).

[3] H.-L. Fu and W.-H. Hu, Ascending subgraph decompositions of regular graphs, Discrete Math. 253 (2002) 11–18. https://doi.org/10.1016/S0012-365X(01)00445-9

[4] C. Huang, A. Kotzig and A. Rosa, On a variation of the Oberwolfach problem, Discrete Math. 27 (1979) 261–277. https://doi.org/10.1016/0012-365X(79)90162-6

[5] J. Liu, The equipartite Oberwolfach problem with uniform tables, J. Combin. Theory Ser. A 101 (2003) 20–34. https://doi.org/10.1016/S0097-3165(02)00011-0

[6] J. Moon, Topics on Tournaments (Holt, Rinehart and Winston, New York, 1968).

[7] B.C. Wagner, Ascending subgraph decompositions of tournaments of order 6 n + 3, Graphs Combin. 29 (2013) 1951–1959. https://doi.org/10.1007/s00373-012-1236-1

[8] B.C. Wagner, Ascending subgraph decompositions of tournaments of orders 6 n + 2 and 6 n + 1, Graphs Combin. 32 (2016) 813–822. https://doi.org/10.1007/s00373-015-1591-9

[9] B.C. Wagner, Ascending subgraph decompositions in oriented complete balanced tripartite graphs, Graphs Combin. 29 (2013) 1549–1555. https://doi.org/10.1007/s00373-012-1208-5