On P_4-tidy graphs
We study the P_4-tidy graphs, a new class defined by Rusu [30] in order to illustrate the notion of P_4-domination in perfect graphs. This class strictly contains the P_4-extendible graphs and the P_4-lite graphs defined by Jamison & Olariu in [19] and [23] and we show that the P_4-tidy graphs a...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
1997-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/232/pdf |
| _version_ | 1797270228493664256 |
|---|---|
| author | V. Giakoumakis F. Roussel H. Thuillier |
| author_facet | V. Giakoumakis F. Roussel H. Thuillier |
| author_sort | V. Giakoumakis |
| collection | DOAJ |
| description | We study the P_4-tidy graphs, a new class defined by Rusu [30] in order to illustrate the notion of P_4-domination in perfect graphs. This class strictly contains the P_4-extendible graphs and the P_4-lite graphs defined by Jamison & Olariu in [19] and [23] and we show that the P_4-tidy graphs and P_4-lite graphs are closely related. Note that the class of P_4-lite graphs is a class of brittle graphs strictly containing the P_4-sparse graphs defined by Hoang in [14]. McConnel & Spinrad [2] and independently Cournier & Habib [5] have shown that the modular decomposition tree of any graph is computable in linear time. For recognizing in linear time P_4-tidy graphs, we apply a method introduced by Giakoumakis in [9] and Giakoumakis & Fouquet in [6] using modular decomposition of graphs and we propose linear algorithms for optimization problems on such graphs, as clique number, stability number, chromatic number and scattering number. We show that the Hamiltonian Path Problem is linear for this class of graphs. Our study unifies and generalizes previous results of Jamison & Olariu ([18], [21], [22]), Hochstattler & Schindler[16], Jung [25] and Hochstattler & Tinhofer [15]. |
| first_indexed | 2024-04-25T02:00:56Z |
| format | Article |
| id | doaj.art-b2b6fc2f300d4ceeb840e065e1776653 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:00:56Z |
| publishDate | 1997-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-b2b6fc2f300d4ceeb840e065e17766532024-03-07T14:56:02ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80501997-01-01Vol. 110.46298/dmtcs.232232On P_4-tidy graphsV. Giakoumakis0https://orcid.org/0000-0002-2194-2342F. Roussel1H. Thuillier2Laboratoire de Recherche en Informatique d'AmiensLaboratoire d'Informatique Fondamentale d'OrléansLaboratoire d'Informatique Fondamentale d'OrléansWe study the P_4-tidy graphs, a new class defined by Rusu [30] in order to illustrate the notion of P_4-domination in perfect graphs. This class strictly contains the P_4-extendible graphs and the P_4-lite graphs defined by Jamison & Olariu in [19] and [23] and we show that the P_4-tidy graphs and P_4-lite graphs are closely related. Note that the class of P_4-lite graphs is a class of brittle graphs strictly containing the P_4-sparse graphs defined by Hoang in [14]. McConnel & Spinrad [2] and independently Cournier & Habib [5] have shown that the modular decomposition tree of any graph is computable in linear time. For recognizing in linear time P_4-tidy graphs, we apply a method introduced by Giakoumakis in [9] and Giakoumakis & Fouquet in [6] using modular decomposition of graphs and we propose linear algorithms for optimization problems on such graphs, as clique number, stability number, chromatic number and scattering number. We show that the Hamiltonian Path Problem is linear for this class of graphs. Our study unifies and generalizes previous results of Jamison & Olariu ([18], [21], [22]), Hochstattler & Schindler[16], Jung [25] and Hochstattler & Tinhofer [15].https://dmtcs.episciences.org/232/pdfgraph modular decompositionperfection p_4-structure[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | V. Giakoumakis F. Roussel H. Thuillier On P_4-tidy graphs Discrete Mathematics & Theoretical Computer Science graph modular decomposition perfection p_4-structure [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | On P_4-tidy graphs |
| title_full | On P_4-tidy graphs |
| title_fullStr | On P_4-tidy graphs |
| title_full_unstemmed | On P_4-tidy graphs |
| title_short | On P_4-tidy graphs |
| title_sort | on p 4 tidy graphs |
| topic | graph modular decomposition perfection p_4-structure [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/232/pdf |
| work_keys_str_mv | AT vgiakoumakis onp4tidygraphs AT froussel onp4tidygraphs AT hthuillier onp4tidygraphs |