<p><em>I update my reply in light of Aravind's comment. The claim in my previous answer was clearly incorrect but, in my defence, I never had a good intuition about graphs.</em></p>

<p>By adapting Aravind's argument you can show an upper bound of $O(\sqrt{n})$, as every $n$-vertex perfect graph has an independent set or a clique of size $\sqrt{n}$. It should be possible to show the tightness of the bound by reasoning on the tree-representation of the cograph. Consider for instance a complete binary tree $T$ with $N = 2^n$ vertices, and label its nodes as series/parallel in an alternating fashion. It represents a cograph $G$, and any $P_3$-free subgraph $H$ of $G$ must span a subtree of $T$ that does not contain three alternations along a root-leaf path; it should imply that this graph may have at most $O(\sqrt{N})$ vertices, but I leave the details to you.</p>

<p>A related question would be to look for a partition in bicluster graphs, as they are exactly the bipartite $P_4$-free graphs. Observe that this problem can be solved in polynomial time by computing the chromatic number of the graph: an arbitrary pairing between color classes then gives the optimal partition.</p>

CC BY-SA 3.0
2014-04-03T23:50:38.280Z
I do not see why "any $P_3$-free subgraph $H$ of $G$ must span a subtree of $T$ that does not contain three alternations along a root-leaf path". Because, an induced subgraph of $G$ need not to be an induced subtree of $T$.
Peng Zhang
CC BY-SA 3.0
2014-04-03T23:59:53.197Z
Please check the wikipedia entry on cographs if you're not familiar with their tree-representation (also called 'cotree'). You need the following observation: given two cographs $G,H$ with $H$ an induced subgraph of $G$, it must hold that $T_H$ is 'embeddable' in $T_G$ in some precise sense. In particular, if $H$ is $P_3$-free then $T_H$ has height at most 2, and when embedding it into $T_G$ we cannot get something too complicated - try figuring the details yourself to get some intuition.
NisaiVloot
CC BY-SA 3.0
2014-04-04T00:03:36.140Z
Thank you, I see it. A $P_3$ happens if a root-to-leaf has at least one 0 and one 1.
Peng Zhang
CC BY-SA 3.0
2014-04-03T10:33:24.443Z
2014-04-03T10:58:04.300Z
2014-04-03T10:58:04.300Z
NisaiVloot
<p>A graph $G$ is $P_k$-free if and only if $G$ does not have an induced subgraph isomorphic to a path of $k$ vertices. Thus, $P_2$-free graphs are exactly <a href="http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29" rel="nofollow">independent sets</a> (or stable sets). $P_4$-free graphs are exactly <a href="http://en.wikipedia.org/wiki/Cograph" rel="nofollow">cographs</a>. </p>

<p><strong>Question.</strong> In the worst case, how many $P_3$-free graphs are necessarily needed to partition a $P_4$-free graph of $n$ vertices? </p>

<p>A trivial upperbound is $\frac{n}{2}$. Because graphs of 2 vertices are trivially $P_3$-free, so we can simply partition any graph of $n$ vertices into $\frac{n}{2}$ components with each component having 2 vertices. </p>

<p>A <a href="http://en.wikipedia.org/wiki/Clique_cover_problem" rel="nofollow">clique-cover number</a> is also an upperbound because clique is also $P_3$-free.</p>

CC BY-SA 3.0
2014-04-03T10:41:18.717Z
A graph on $n$ vertices contains a clique or an independent set of size $\Omega(\log n)$. By removing this repeatedly, I guess an upper bound of $O(\frac{n}{\log n})$ should be possible.
Aravind
<graph-theory><graph-algorithms><co.combinatorics><extremal-combinatorics><cograph>
Upperbound the order of P3-free partition of P4-free graphs
Peng Zhang
# Upperbound the order of P3-free partition of P4-free graphs

(Asked by: username_0 on 2014-04-03)

A graph $G$ is $P\_k$-free if and only if $G$ does not have an induced subgraph isomorphic to a path of $k$ vertices. Thus, $P\_2$-free graphs are exactly [independent sets](http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29) (or stable sets). $P\_4$-free graphs are exactly [cographs](http://en.wikipedia.org/wiki/Cograph).

**Question.** In the worst case, how many $P\_3$-free graphs are necessarily needed to partition a $P\_4$-free graph of $n$ vertices?

A trivial upperbound is $\frac{n}{2}$. Because graphs of 2 vertices are trivially $P\_3$-free, so we can simply partition any graph of $n$ vertices into $\frac{n}{2}$ components with each component having 2 vertices.

A [clique-cover number](http://en.wikipedia.org/wiki/Clique_cover_problem) is also an upperbound because clique is also $P\_3$-free.

**Tags:** graph-theory, graph-algorithms, co.combinatorics, extremal-combinatorics, cograph
> **Comments:**
> **username_1**: A graph on $n$ vertices contains a clique or an independent set of size $\Omega(\log n)$. By removing this repeatedly, I guess an upper bound of $O(\frac{n}{\log n})$ should be possible.  

---

## 1 answers

### Answer by username_2 on 2014-04-03. Score: 2 | Accepted answer

*I update my reply in light of Aravind's comment. The claim in my previous answer was clearly incorrect but, in my defence, I never had a good intuition about graphs.*

By adapting Aravind's argument you can show an upper bound of $O(\sqrt{n})$, as every $n$-vertex perfect graph has an independent set or a clique of size $\sqrt{n}$. It should be possible to show the tightness of the bound by reasoning on the tree-representation of the cograph. Consider for instance a complete binary tree $T$ with $N = 2^n$ vertices, and label its nodes as series/parallel in an alternating fashion. It represents a cograph $G$, and any $P\_3$-free subgraph $H$ of $G$ must span a subtree of $T$ that does not contain three alternations along a root-leaf path; it should imply that this graph may have at most $O(\sqrt{N})$ vertices, but I leave the details to you.

A related question would be to look for a partition in bicluster graphs, as they are exactly the bipartite $P\_4$-free graphs. Observe that this problem can be solved in polynomial time by computing the chromatic number of the graph: an arbitrary pairing between color classes then gives the optimal partition.

> **Comments:**
> **username_0**: I do not see why "any $P_3$-free subgraph $H$ of $G$ must span a subtree of $T$ that does not contain three alternations along a root-leaf path". Because, an induced subgraph of $G$ need not to be an induced subtree of $T$.  
> **username_2**: Please check the wikipedia entry on cographs if you're not familiar with their tree-representation (also called 'cotree'). You need the following observation: given two cographs $G,H$ with $H$ an induced subgraph of $G$, it must hold that $T_H$ is 'embeddable' in $T_G$ in some precise sense. In particular, if $H$ is $P_3$-free then $T_H$ has height at most 2, and when embedding it into $T_G$ we cannot get something too complicated - try figuring the details yourself to get some intuition.  
> **username_0**: Thank you, I see it. A $P_3$ happens if a root-to-leaf has at least one 0 and one 1.  

---

