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

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

dc.contributor.author	Abu-Khzam, Faisal N.
dc.contributor.author	Feghali, Carl
dc.contributor.author	Muller, Haiko
dc.date.accessioned	2018-04-26T06:12:56Z
dc.date.available	2018-04-26T06:12:56Z
dc.date.copyright	2014	en_US
dc.date.issued	2018-04-26
dc.identifier.uri	http://hdl.handle.net/10725/7592
dc.description.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.	en_US
dc.language.iso	en	en_US
dc.title	Forbidden subgraph characterization of (P3-free, K3-free)-colourable cographs	en_US
dc.type	Article	en_US
dc.description.version	Pre-print	en_US
dc.author.school	SAS	en_US
dc.author.idnumber	200302941	en_US
dc.author.department	Computer Science and Mathematics	en_US
dc.description.embargo	N/A	en_US
dc.journal.volume	2	en_US
dc.journal.issue	1403.5961	en_US
dc.identifier.ctation	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.	en_US
dc.author.email	faisal.abukhzam@lau.edu.lb	en_US
dc.identifier.tou	http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php	en_US
dc.identifier.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	en_US
dc.orcid.id	https://orcid.org/0000-0001-5221-8421	en_US
dc.author.affiliation	Lebanese American University	en_US