Forbidden subgraph characterization of (P3-free, K3-free)-colourable cographs
A (P3-free, K3-free)-colouring of a graph G = (V, E) is a partition of V = A ∪ B such that G[A] is P3-free and G[B] is K3-free. This problem is known to be NP-complete even when restricted to planar graphs and perfect graphs. In this paper, we provide a finite list of 17 forbidden induced subgraphs...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | article |
| Published: |
2014
|
| Online Access: | http://hdl.handle.net/10725/7592 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://www.researchgate.net/profile/Faisal_Abu-khzam/publication/261100677_Forbidden_subgraph_characterization_of_P_3-free_K_3-free-colourable_cographs/links/02e7e536938e11d9a1000000.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | A (P3-free, K3-free)-colouring of a graph G = (V, E) is a partition of V = A ∪ B such that G[A] is P3-free and G[B] is K3-free. This problem is known to be NP-complete even when restricted to planar graphs and perfect graphs. In this paper, we provide a finite list of 17 forbidden induced subgraphs for cographs with a (P3-free, K3-free)- colouring. This yields a linear time recognition algorithm. |
|---|