Skip to main content
2 of 3
Removed the deprecated (discrete-mathematics) tag - see the tag info: https://mathoverflow.net/tags/discrete-mathematics/info (if there are some other suitable tags, choose some of them instead)
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

$\{ P_3, P_4 \}$-factor

Definition. A graph $G=(V,E)$ is to be $\{d_1,\dots,d_n\}$-graph if for each vertex $v\in V$ we have $\text{deg}(v)=d_i$ for some $i=1,\dots n$.

Definition. A connected graph $G=(V,E)$ is called $n$-connected (for n\geq 2) whenever if we remove $n-1$ vertices then the graph is still connected.

Definition. A $P_k$-factor of a graph $G=(V,E)$ is a spanning subgraph of $G$ such that each component of which is $P_k$, the path on $k$ vertices. We say that $G$ has a $P_k$-factorization if $E$ can be partitioned into $P_k$-factors

Question. Let $G$ be a $\{2,3\}$-graph which is also 2-connected. Does $G$ have $\{ P_3, P_4 \}$-factor?