Forbidden subgraph characterization of (P3-free, K3-free)-colourable cographs

Abu-Khzam, Faisal N.; Feghali, Carl; Muller, Haiko

Forbidden subgraph characterization of (P3-free, K3-free)-colourable cographs

Abu-Khzam, Faisal N.; Feghali, Carl; Muller, Haiko

URL: 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

Date: 2018-04-26

Terms of Use: This item is made available under the terms and conditions applicable to " Article ", as set forth at: http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php

Abstract:

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.

Citation:

Feghali, C., Abu-Khzam, F. N., & Müller, H. (2014). Forbidden Subgraph Characterization of (P3-free, K3-free)-colourable Cographs. arXiv preprint arXiv:1403.5961.