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!
|
| _version_ | 1864513482420912128 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Feghali, Carl Muller, Haiko |
| author2_role | author author |
| author_facet | Abu-Khzam, Faisal N. Feghali, Carl Muller, Haiko |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Feghali, Carl Muller, Haiko |
| dc.date.none.fl_str_mv | 2014 2018-04-26T06:12:56Z 2018-04-26T06:12:56Z 2018-04-26 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/7592 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. 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 |
| dc.language.none.fl_str_mv | en |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | Forbidden subgraph characterization of (P3-free, K3-free)-colourable cographs |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_317cac2b9ec9f76790f552b222b4fb2d |
| identifier_str_mv | 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. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/7592 |
| publishDate | 2014 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Forbidden subgraph characterization of (P3-free, K3-free)-colourable cographsAbu-Khzam, Faisal N.Feghali, CarlMuller, HaikoA (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.Pre-printN/A2018-04-26T06:12:56Z2018-04-26T06:12:56Z20142018-04-26Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/articlehttp://hdl.handle.net/10725/7592Feghali, C., Abu-Khzam, F. N., & Müller, H. (2014). Forbidden Subgraph Characterization of (P3-free, K3-free)-colourable Cographs. arXiv preprint arXiv:1403.5961.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://www.researchgate.net/profile/Faisal_Abu-khzam/publication/261100677_Forbidden_subgraph_characterization_of_P_3-free_K_3-free-colourable_cographs/links/02e7e536938e11d9a1000000.pdfeninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/75922021-03-19T10:43:13Z |
| spellingShingle | Forbidden subgraph characterization of (P3-free, K3-free)-colourable cographs Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | Forbidden subgraph characterization of (P3-free, K3-free)-colourable cographs |
| title_full | Forbidden subgraph characterization of (P3-free, K3-free)-colourable cographs |
| title_fullStr | Forbidden subgraph characterization of (P3-free, K3-free)-colourable cographs |
| title_full_unstemmed | Forbidden subgraph characterization of (P3-free, K3-free)-colourable cographs |
| title_short | Forbidden subgraph characterization of (P3-free, K3-free)-colourable cographs |
| title_sort | Forbidden subgraph characterization of (P3-free, K3-free)-colourable cographs |
| url | 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 |