episciences.org_232_20230328202132168
20230328202132168
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
01
01
1997
Vol. 1
On P_4tidy graphs
V.
Giakoumakis
F.
Roussel
H.
Thuillier
We study the P_4tidy graphs, a new class defined by Rusu [30] in order to illustrate the notion of P_4domination in perfect graphs. This class strictly contains the P_4extendible graphs and the P_4lite graphs defined by Jamison & Olariu in [19] and [23] and we show that the P_4tidy graphs and P_4lite graphs are closely related. Note that the class of P_4lite graphs is a class of brittle graphs strictly containing the P_4sparse 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_4tidy 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].
01
01
1997
232
https://hal.science/hal00955688v1
10.46298/dmtcs.232
https://dmtcs.episciences.org/232

https://dmtcs.episciences.org/232/pdf

https://dmtcs.episciences.org/232/pdf