2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Aravind
    Apr 3, 2014 at 10:41

1 Answer 1

Reset to default
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.