Questions tagged [cograph]
The cograph tag has no usage guidance.
3
questions
2
votes
1
answer
511
views
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 ...
- 1,443
8
votes
3
answers
247
views
On the size of P4-transversals of graphs
A subset $T$ of vertices of a graph $G$ is called a $P_4$-transversal if $T$ intersects every $P_4$ of $G$. In the context of this question, we consider $P_4$ as an induced path on 4 vertices.
...
- 1,443
7
votes
1
answer
404
views
Chromatic number of G+v where G is a cograph
Cograph is a well-know graph that does not have induced $P_4$. My questions are about determining the chromatic number of graphs in the class cograph+v.
Notations:
Denote by $\chi(G)$ the chromatic ...
- 1,443