Discrete Mathematics & Theoretical Computer Science
Volume 1 n° 1 (1997), pp. 17-41
| author: | V Giakoumakis and F Roussel and H Thuillier |
|---|---|
| title: | On P4-tidy graphs |
| keywords: | graph modular decomposition perfection P4-structure |
| abstract: | We study the P4-tidy graphs, a new class defined by Rusu [30] in order to illustrate the notion of P4-domination in perfect graphs. This class strictly contains the P4-extendible graphs and the P4-lite graphs defined by Jamison & Olariu in [19] and [23] and we show that the P4-tidy graphs and P4-lite graphs are closely related. Note that the class of P4-lite graphs is a class of brittle graphs strictly containing the P4-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 P4-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]. |
| reference: | V Giakoumakis and F Roussel and H Thuillier (1997), On P4-tidy graphs, Discrete Mathematics and Theoretical Computer Science 1, pp. 17-41 |
| ps.gz-source: | dm010102.ps.gz |
| ps-source: | dm010102.ps ( 651 K ) |
| pdf-source: | dm010102.pdf (286 K) |
The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.
Automatically produced on Tue Jan 19 17:48:59 MET 1999 by gustedt