Towards a conjecture of Woodall for partial 3-trees (2024)

Case 1:

There exists a ditriangle in $G$ that is a separator (in the underlying graph), say$abc$.

Let$G_{1}$ and$G_{2}$ be the digraphs whose underlying graphs are planar 3-trees and$V(G_{1})\cap V(G_{2})=\{a,b,c\}$.By induction hypothesis,$G_{1}$ has a packing$\{T_{1},T_{2},T_{3}\}$and$G_{2}$ has a packing$\{T^{\prime}_{1},T^{\prime}_{2},T^{\prime}_{3}\}$.We may assume, without loss of generality, that$T_{1}\cap T^{\prime}_{1}=\{ab\}$,$T_{2}\cap T^{\prime}_{2}=\{bc\}$ and$T_{3}\cap T^{\prime}_{3}=\{ac\}$. We will show that$\{T_{1}\cup T^{\prime}_{1},T_{2}\cup T^{\prime}_{2},T_{3}\cup T^{\prime}_{3}\}$ is a packing of$G$.Let$C$ be a dicycle in$G$. If either$V(C)\subseteq V(G_{1})$ or$V(C)\subseteq V(G_{2})$, then we are done.Hence, we may assume that$V(C)\cap V(G_{1})\neq\emptyset$and$V(C)\cap V(G_{2})\neq\emptyset$.This implies that${|V(C)\cap\{a,b,c\}|\geq 2}$.

First suppose that$|V(C)\cap\{a,b,c\}|=2$,and, without loss of generality, that$V(C)\cap\{a,b,c\}=\{a,b\}$.Let$C_{1}$ and$C_{2}$ be the two$ab$-parts of$C$,with $V(C_{1})\subseteq V(G_{1})$ and$V(C_{2})\subseteq V(G_{2})$.Suppose without loss of generalitythat$C_{1}$ starts at $a$ and ends at $b$.Note that$C_{1}\cdot bca$ is a dicyclein$G_{1}$ and that$C_{2}\cdot ab$ is a dicycle in$G_{2}$.Hence,$C_{1}\cap T_{1}\neq\emptyset$and$C_{2}\cap T^{\prime}_{2},C_{2}\cap T^{\prime}_{3}\neq\emptyset$,and we are done(Figure 2($a$)).

Now suppose that$|V(C)\cap\{a,b,c\}|=3$.First suppose thatthe dipath from $a$ to $c$ in $C$ contains $b$.Let$C_{ab},C_{bc},C_{ca}$ be the corresponding$abc$-partsof$C$. Without loss of generality, we may assumethat$V(C_{ab})\subseteq V(G_{1})$ and$V(C_{bc}),V(C_{ca})\subseteq V(G_{2})$.Note that$C_{ab}\cdot bca$ is a dicyclein$G_{1}$ and that$C_{bc}\cdot C_{ca}\cdot ab$ is a dicycle in$G_{2}$.Hence,$C_{1}\cap T_{1}\neq\emptyset$and$C_{2}\cap T^{\prime}_{2},C_{2}\cap T^{\prime}_{3}\neq\emptyset$and we are done(Figure 2($b$)).

Now suppose thatthe dipath from $a$ to $b$ in $C$ contains $c$.Let$C_{cb},C_{ba},C_{ac}$ be the corresponding$cba$-partsof$C$. Without loss of generality, we may assumethat$V(C_{ba})\subseteq V(G_{1})$ and$V(C_{ac}),V(C_{cb})\subseteq V(G_{2})$.Note that$C_{ab}\cdot ba$ is a dicyclein$G_{1}$ and that$C_{ac}\cdot ca$ is a dicycle in$G_{2}$.Hence,$C_{1}\cap T_{2},T_{3}\neq\emptyset$and$C_{2}\cap T_{1}\neq\emptyset$ and we are done(Figure 2($c$)).

Case 2:

There exists no ditriangle in $G$ that is a separator (in the underlying graph).

Let$G^{\prime}=G-V_{3}$. In this case, we let$T_{1}=E(G^{\prime})$and define$T_{2}$ and$T_{3}$ according to the next rule.Let$u\in V_{3}$ and suppose that the neighbors of $u$ in the underlying 3-tree are $a,b$ and $c$.Note that$\{a,b,c\}$ does not induce a ditriangle in $G$.Indeed, otherwise$abc$ is a separator in$G$.Thus, we may assume that$ab,bc,ac\in E(G)$.If the digraph induced by $\{a,b,c\}$ has no ditriangle, then we addall incident arcs of$u$ to$T_{1}$.Otherwise, if$xyu$ is a ditriangle, with$x,y\in\{a,b,c\}$, then we add$yu$ to$T_{2}$ and$ux$ to$T_{3}$.Any other arc is added to$T_{1}$ (Figure 3).

We will show that$\{T_{1},T_{2},T_{3}\}$ is a packing of$G$.Note that, by Proposition 9, the underlying graph of$G^{\prime}$is a planar 3-tree.Thus, by Proposition 10, $G^{\prime}$ has no dicycles; otherwise, as$n>4$, we will have a ditriangle in$G^{\prime}$, which is a separator in the underlying graph of$G$.Let$C$ be a dicycle in$G$. By the previous observation,$V(C)\cap V_{3}\neq\emptyset$.

For each$u\in V_{3}\cap V(C)$, let$e_{u}$ be the arc whose endsare neighbors of$u$ in$C$.Let$D=(C-V_{3})\cup\{e_{u}:u\in V_{3}\}.$As$V(D)\subseteq V(G^{\prime})$,$D$ is not a dicycle by Proposition 10.Hence, there exists$u\in V_{3}\cap V(C)$ such that$e_{u}\cdot u$ is a ditriangle.Thus, by the definition of $T_{2}$ and $T_{3}$,$C\cap T_{2}\neq\emptyset$ and$C\cap T_{3}\neq\emptyset$.If$E(C)\cap E(G^{\prime})\neq\emptyset$, then we are done,as every arc of$G^{\prime}$ is in$T_{1}$.Thus, let us assume that$E(C)\subseteq E(G\setminus G^{\prime})$and suppose by contradiction that$C\cap T_{1}=\emptyset$.This implies, by the definition of $T_{2}$ and $T_{3}$, that$C$ consists of an even sequence of arcs that alternates between arcs in $T_{2}$ and $T_{3}$.But in this case,$D$ is a dicycle in$G^{\prime}$, a contradiction.