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

LAUR Repository

Show simple item record

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.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

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account