4
$\begingroup$

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=(V,E)$ be a $\{2,3\}$-graph which is also 2-connected and $|V|>5$. Does $G$ have $\{ P_3, P_4 \}$-factor?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ How about a triangle? Gerhard "Thinking About Very Small Counterexamples" Paseman, 2018.09.06. $\endgroup$
    – Gerhard Paseman
    Commented Sep 6, 2018 at 23:15
  • $\begingroup$ @GerhardPaseman: Perhaps the OP intends that a $\{2,3\}$ graph must have at least one vertex of deg-$2$ and at least one of deg-$3$? Under this interpretation, a triangle is a $\{2\}$-graph. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 6, 2018 at 23:58
  • $\begingroup$ The Ear decomposition may be helpful. $\endgroup$
    – LeechLattice
    Commented Sep 7, 2018 at 0:38
  • 3
    $\begingroup$ What is a $\{P_3,P_4\}$-factor? $\endgroup$
    – bof
    Commented Sep 7, 2018 at 1:05

1 Answer 1

Reset to default
3
$\begingroup$

I cannot think of a proof or disproof at the moment but in 'Path factors in cubic graphs', Kawarabayashi, Matsuda and Oda proved that every 2-connected cubic graph of order at least six has a {$P_3$,$P_4$}-factor. (Actually, they showed that every such graph has a {$P_k$| $k$≥6}-factor.) I am not sure you can renounce the implicit minimum degree condition and still hope for the same conclusion.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .