# Upperbound the order of P3-free partition of P4-free graphs

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 (or stable sets). $P_4$-free graphs are exactly cographs.

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 is also an upperbound because clique is also $P_3$-free.

• 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 Apr 3 '14 at 10:41

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.
• 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 Apr 3 '14 at 23:50
• 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 Apr 3 '14 at 23:59
• Thank you, I see it. A $P_3$ happens if a root-to-leaf has at least one 0 and one 1. – Peng Zhang Apr 4 '14 at 0:03