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].
Allem, Luiz Emilio; Cafure, Antonio; Dratman, Ezequiel; Grippo, Luciano N.; Safe, MartĂn D.; Trevisan, Vilmar, 2017, On Graphs With A Single Large Laplacian Eigenvalue, Electronic Notes In Discrete Mathematics, 62, pp. 297-302, 10.1016/j.endm.2017.10.051.
Aravind, N.R.; Karthick, T.; Subramanian, C.R., 2011, Bounding Χ In Terms Of Ω And Δ For Some Classes Of Graphs, Discrete Mathematics, 311, 12, pp. 911-920, 10.1016/j.disc.2011.02.021.
Argiroffo, G.; Nasini, G.; Torres, P., 2012, The Packing Coloring Problem For (Q,Q-4) Graphs, Combinatorial Optimization, pp. 309-319, 10.1007/978-3-642-32147-4_28.
Bodlaender, Hans L.; De Figueiredo, Celina M. H.; Gutierrez, Marisa; Kloks, Ton; Niedermeier, Rolf, 2004, Simple Max-Cut For Split-Indifference Graphs And Graphs With Few P 4âS, Experimental And Efficient Algorithms, pp. 87-99, 10.1007/978-3-540-24838-5_7.
Bonomo, Flavia; DurĂĄn, Guillermo; Safe, MartĂn; Wagler, Annegret K., 2009, On Minimal Forbidden Subgraph Characterizations Of Balanced Graphs, Electronic Notes In Discrete Mathematics, 35, pp. 41-46, 10.1016/j.endm.2009.11.008.
Bonomo, Flavia; DurĂĄn, Guillermo; Safe, MartĂn; Wagler, Annegret K., 2014, Clique-perfectness And Balancedness Of Some Graph Classes, International Journal Of Computer Mathematics, 91, 10, pp. 2118-2141, 10.1080/00207160.2014.881994.
Bonomo-Braberman, Flavia; DurĂĄn, Guillermo; Safe, MartĂn D.; Wagler, Annegret K., 2020, On Some Graph Classes Related To Perfect Graphs: A Survey, Discrete Applied Mathematics, 281, pp. 42-60, 10.1016/j.dam.2019.05.019.
Bonomo-Braberman, Flavia; Mazzoleni, MarĂa PĂa; Rean, Mariano Leonardo; Ries, Bernard, 2022, On Some Special Classes Of Contact B0-VPG Graphs, Discrete Applied Mathematics, 308, pp. 111-129, 10.1016/j.dam.2019.10.008.
BreĹĄar, BoĹĄtjan; Kos, Tim; Nasini, Graciela; Torres, Pablo, 2018, Total Dominating Sequences In Trees, Split Graphs, And Under Modular Decomposition, Discrete Optimization, 28, pp. 16-30, 10.1016/j.disopt.2017.10.002.
Courcelle, B.; Makowsky, J. A.; Rotics, U., 1998, Linear Time Solvable Optimization Problems On Graphs Of Bounded Clique Width, Graph-Theoretic Concepts In Computer Science, pp. 1-16, 10.1007/10692760_1.
De Mello, C.P.; Morgana, A.; Liverani, M., 2006, The Clique Operator On Graphs With Few P4's, Discrete Applied Mathematics, 154, 3, pp. 485-492, 10.1016/j.dam.2005.09.002.
Dobson, M.P.; Leoni, V.; Nasini, G., 2010, The K-Limited Packing And K-Tuple Domination Problems In Strongly Chordal, P4-tidy And Split Graphs, Electronic Notes In Discrete Mathematics, 36, pp. 559-566, 10.1016/j.endm.2010.05.071.
Dobson, M.P.; Leoni, V.; Nasini, G., 2011, The Multiple Domination And Limited Packing Problems In Graphs, Information Processing Letters, 111, 23-24, pp. 1108-1113, 10.1016/j.ipl.2011.09.002.
DurĂĄn, Guillermo; Grippo, Luciano N.; Safe, MartĂn, 2011, Probe Interval And Probe Unit Interval Graphs On Superclasses Of Cographs, Electronic Notes In Discrete Mathematics, 37, pp. 339-344, 10.1016/j.endm.2011.05.058.
DurĂĄn, Guillermo; Grippo, Luciano N.; Safe, MartĂn, 2014, Structural Results On Circular-Arc Graphs And Circle Graphs: A Survey And The Main Open Problems, Discrete Applied Mathematics, 164, pp. 427-443, 10.1016/j.dam.2012.12.021.
Faure-Giovagnoli, Pierre; Petit, Jean-Marc; Scuturici, Vasile-Marian, 2022, Assessing The Existence Of A Function In A Dataset With The G3 Indicator, 2022 IEEE 38Th International Conference On Data Engineering (ICDE), 10.1109/icde53745.2022.00050.
Hellmuth, Marc; Scholz, Guillaume E., 2022, From Modular Decomposition Trees To Level-1 Networks: Pseudo-cographs, Polar-Cats And Prime Polar-Cats, Discrete Applied Mathematics, 321, pp. 179-219, 10.1016/j.dam.2022.06.042.
Karthick, T.; Maffray, FrĂŠdĂŠric, 2015, Vizing Bound For The Chromatic Number On Some Graph Classes, Graphs And Combinatorics, 32, 4, pp. 1447-1460, 10.1007/s00373-015-1651-1.
Klein, S.; De Mello, C. P.; Morgana, A., 2011, Recognizing Well Covered Graphs Of Families With Special P 4-Components, Graphs And Combinatorics, 29, 3, pp. 553-567, 10.1007/s00373-011-1123-1.
Klein, Sulamita; Morgana, Aurora, 2011, On Clique-Colouring Of Graphs With Few P4âs, Journal Of The Brazilian Computer Society, 18, 2, pp. 113-119, 10.1007/s13173-011-0053-3.
Linhares-Sales, ClĂĄudia; Maia, Ana Karolinna; Martins, Nicolas; Sampaio, Rudini, 2014, Restricted Coloring Problems On Graphs With Few P 4âS, Annals Of Operations Research, 217, 1, pp. 385-397, 10.1007/s10479-014-1537-2.
Nasini, Graciela; Torres, Pablo, 2015, Some Links Between Identifying Codes And Separating, Dominating And Total Dominating Sets In Graphs, Electronic Notes In Discrete Mathematics, 50, pp. 181-186, 10.1016/j.endm.2015.07.031.
Nikolopoulos, Stavros D.; Palios, Leonidas; Papadopoulos, Charis, 2011, Counting Spanning Trees In Graphs Using Modular Decomposition, WALCOM: Algorithms And Computation, pp. 202-213, 10.1007/978-3-642-19094-0_21.
Nikolopoulos, Stavros D.; Palios, Leonidas; Papadopoulos, Charis, 2014, Counting Spanning Trees Using Modular Decomposition, Theoretical Computer Science, 526, pp. 41-57, 10.1016/j.tcs.2014.01.012.
Velasquez, Clara InĂŠs Betancur; Bonomo-Braberman, Flavia; Koch, Ivo, 2011, On The B-Coloring Of P4-tidy Graphs, Discrete Applied Mathematics, 159, 1, pp. 60-68, 10.1016/j.dam.2010.10.002.