Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On P_4-tidy graphs
Article

On P_4-tidy graphs

V. Giakoumakis ORCID (1), F. Roussel (2), H. Thuillier (2)
(1) Laboratoire de Recherche en Informatique d'Amiens
(2) Laboratoire d'Informatique Fondamentale d'Orléans
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 1997
Last modified on
March 31, 2025
Volume 1
vol. 1
DOI
10.46298/dmtcs.232
License
https://about.hal.science/hal-authorisation-v1
Indicators
952
Views
767
Downloads

On P_4-tidy graphs

V. Giakoumakis ORCID (1), F. Roussel (2), H. Thuillier (2)
(1) Laboratoire de Recherche en Informatique d'Amiens
(2) Laboratoire d'Informatique Fondamentale d'Orléans
Abstract
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].
Keywords
English
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
French
  • graph modular decomposition
  • perfection P_4-structure
Cited by

Source: OpenCitations

  • Relationships between scattering number and other vulnerability parameters

    International Journal of Computer Mathematics

    Authors : Shenggui Zhang ORCID, Shuying Peng

    Journal reference : Volume 81, 2004, pp. 291-298

    DOI : 10.1080/00207160410001661690

  • On minimal forbidden subgraph characterizations of balanced graphs

    Repositorio Digital Institucional de la Universidad de Buenos Aires (Universidad de Buenos Aires)

    Authors : Flavia Bonomo ORCID, Guillermo Durán ORCID, Martín D. Safe ORCID, Annegret K. Wagler ORCID

    Journal reference : Volume 35, 2009, pp. 41-46

    DOI : 10.1016/j.endm.2009.11.008

  • Assessing the Existence of a Function in a Dataset with the g3 Indicator

    Authors : Pierre Faure-Giovagnoli ORCID, Jean-Marc Petit ORCID, Vasile-Marian Scuturici ORCID

    Journal reference : Volume , 2022, pp. 607-620

    DOI : 10.1109/icde53745.2022.00050

  • On clique-colouring of graphs with few P4’s

    Journal of the Brazilian Computer Society

    Authors : Sulamita Klein ORCID, Aurora Morgana

    Journal reference : Volume 18, 2011, pp. 113-119

    DOI : 10.1007/s13173-011-0053-3

  • Problema de partição em conjunto independente e árvore quando restrito à classe dos grafos-P4-tidy

    Anais do III Encontro de Teoria da Computação (ETC 2018)

    Authors : Fábio Silva ORCID, Raquel Bravo ORCID, Rodolfo Oliveira, Uéverton Souza ORCID

    Journal reference : Volume , 2018, pp. 21-24

    DOI : 10.5753/etc.2018.3142

  • On graphs with a single large Laplacian eigenvalue

    Electronic Notes in Discrete Mathematics

    Authors : L. Emilio Allem ORCID, Antonio Cafure, Ezequiel Dratman ORCID, Luciano N. Grippo ORCID, Martín D. Safe ORCID, Vilmar Trevisan ORCID

    Journal reference : Volume 62, 2017, pp. 297-302

    DOI : 10.1016/j.endm.2017.10.051

  • b -coloring of tight graphs

    Discrete Applied Mathematics

    Authors : Frédéric Havet ORCID, Cláudia Linhares Sales ORCID, Leonardo Sampaio ORCID

    Journal reference : Volume 160, 2011, pp. 2709-2715

    DOI : 10.1016/j.dam.2011.10.017

  • On the b -coloring of P4 -tidy graphs

    CONICET Digital (CONICET)

    Authors : Clara Inés Betancur Velasquez, Flavia Bonomo ORCID, Ivo Koch

    Journal reference : Volume 159, 2010, pp. 60-68

    DOI : 10.1016/j.dam.2010.10.002

  • Partial characterizations of circle graphs

    Americanae (AECID Library)

    Authors : Flavia Bonomo ORCID, Guillermo Durán ORCID, Luciano N. Grippo ORCID, Martín D. Safe ORCID

    Journal reference : Volume 159, 2010, pp. 1699-1706

    DOI : 10.1016/j.dam.2010.06.020

  • Some links between identifying codes and separating, dominating and total dominating sets in graphs

    Electronic Notes in Discrete Mathematics

    Authors : Graciela Nasini, Pablo Torres ORCID

    Journal reference : Volume 50, 2015, pp. 181-186

    DOI : 10.1016/j.endm.2015.07.031

  • On some graph classes related to perfect graphs: A survey

    Authors : Flavia Bonomo-Braberman ORCID, Guillermo Durán ORCID, Martín D. Safe ORCID, Annegret K. Wagler ORCID

    Journal reference : Volume 281, 2019, pp. 42-60

    DOI : 10.1016/j.dam.2019.05.019

  • Structural results on circular-arc graphs and circle graphs: A survey and the main open problems

    Discrete Applied Mathematics

    Authors : Guillermo Durán ORCID, Luciano N. Grippo ORCID, Martín D. Safe ORCID

    Journal reference : Volume 164, 2013, pp. 427-443

    DOI : 10.1016/j.dam.2012.12.021

  • First-Fit coloring of {P5,K4−e} -free graphs

    Discrete Applied Mathematics

    Authors : S.A. Choudum, T. Karthick

    Journal reference : Volume 158, 2010, pp. 620-626

    DOI : 10.1016/j.dam.2009.12.009

  • Partitioning P4 -tidy graphs into a stable set and a forest

    Discrete Applied Mathematics

    Authors : Raquel Bravo ORCID, Rodolfo Oliveira, Fábio da Silva ORCID, Uéverton S. Souza ORCID

    Journal reference : Volume 338, 2023, pp. 22-29

    DOI : 10.1016/j.dam.2023.05.016

  • From modular decomposition trees to level-1 networks: Pseudo-cographs, polar-cats and prime polar-cats

    Discrete Applied Mathematics

    Authors : Marc Hellmuth ORCID, Guillaume E. Scholz ORCID

    Journal reference : Volume 321, 2022, pp. 179-219

    DOI : 10.1016/j.dam.2022.06.042

  • Classes of perfect graphs

    Discrete Mathematics

    Authors : Stefan Hougardy ORCID

    Journal reference : Volume 306, 2006, pp. 2529-2571

    DOI : 10.1016/j.disc.2006.05.021

  • ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S

    International Journal of Foundations of Computer Science

    Authors : J. A. MAKOWSKY, U. ROTICS

    Journal reference : Volume 10, 1999, pp. 329-348

    DOI : 10.1142/s0129054199000241

  • Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs

    ACM Transactions on Algorithms

    Authors : David Coudert ORCID, Guillaume Ducoffe ORCID, Alexandru Popa ORCID

    Journal reference : Volume 15, 2019, pp. 1-57

    DOI : 10.1145/3310228

  • The clique operator on graphs with few P4 's

    Discrete Applied Mathematics

    Authors : C.P. de Mello, A. Morgana, M. Liverani ORCID

    Journal reference : Volume 154, 2005, pp. 485-492

    DOI : 10.1016/j.dam.2005.09.002

  • The multiple domination and limited packing problems in graphs

    Information Processing Letters

    Authors : M.P. Dobson, V. Leoni, G. Nasini

    Journal reference : Volume 111, 2011, pp. 1108-1113

    DOI : 10.1016/j.ipl.2011.09.002

  • Recognizing Well Covered Graphs of Families with Special P 4-Components

    Graphs and Combinatorics

    Authors : S. Klein ORCID, C. P. de Mello, A. Morgana

    Journal reference : Volume 29, 2011, pp. 553-567

    DOI : 10.1007/s00373-011-1123-1

  • Grundy Double Domination Number: Bounds, Graph Operations, and Efficient Computation for $$P_4$$-Tidy Graphs

    Bulletin of the Malaysian Mathematical Sciences Society

    Authors : Pablo Torres

    Journal reference : Volume 49, 2026, pp.

    DOI : 10.1007/s40840-026-02055-z

  • An O(n) time algorithm for maximum matching in P4-tidy graphs

    Information Processing Letters

    Authors : J.L. Fouquet, I. Parfenoff, H. Thuillier

    Journal reference : Volume 62, 1997, pp. 281-287

    DOI : 10.1016/s0020-0190(97)00081-1

  • On some special classes of contact B 0 -VPG graphs

    Discrete Applied Mathematics

    Authors : Flavia Bonomo-Braberman ORCID, María Pía Mazzoleni ORCID, Mariano Leonardo Rean, Bernard Ries ORCID

    Journal reference : Volume 308, 2019, pp. 111-129

    DOI : 10.1016/j.dam.2019.10.008

  • SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s

    Electronic Notes in Discrete Mathematics

    Authors : Hans L. Bodlaender ORCID, Ton Kloks ORCID, Rolf Niedermeier ORCID

    Journal reference : Volume 3, 1999, pp. 19-26

    DOI : 10.1016/s1571-0653(05)80014-9

  • The Packing Coloring Problem for (q,q-4) Graphs

    Lecture notes in computer science

    Authors : G. Argiroffo, G. Nasini, P. Torres ORCID

    Journal reference : Volume , 2012, pp. 309-319

    DOI : 10.1007/978-3-642-32147-4_28

  • A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs

    Networks

    Authors : Katerina Asdre, Stavros D. Nikolopoulos ORCID

    Journal reference : Volume 50, 2007, pp. 231-240

    DOI : 10.1002/net.20200

  • Probe interval and probe unit interval graphs on superclasses of cographs

    Electronic Notes in Discrete Mathematics

    Authors : Guillermo Durán ORCID, Luciano N. Grippo ORCID, Martín D. Safe ORCID

    Journal reference : Volume 37, 2011, pp. 339-344

    DOI : 10.1016/j.endm.2011.05.058

  • Simple Max-Cut for Split-Indifference Graphs and Graphs with Few P 4’s

    Lecture notes in computer science

    Authors : Hans L. Bodlaender ORCID, Celina M. H. de Figueiredo ORCID, Marisa Gutierrez ORCID, Ton Kloks ORCID, Rolf Niedermeier ORCID

    Journal reference : Volume , 2004, pp. 87-99

    DOI : 10.1007/978-3-540-24838-5_7

  • An optimal parallel solution for the path cover problem on -sparse graphs

    Journal of Parallel and Distributed Computing

    Authors : Katerina Asdre, Stavros D. Nikolopoulos ORCID, Charis Papadopoulos ORCID

    Journal reference : Volume 67, 2006, pp. 63-76

    DOI : 10.1016/j.jpdc.2006.08.011

  • Clique-width of partner-limited graphs

    Discrete Mathematics

    Authors : Jean-Marie Vanherpe

    Journal reference : Volume 276, 2003, pp. 363-374

    DOI : 10.1016/s0012-365x(03)00295-4

  • Restricted coloring problems on graphs with few

    Authors : V. Campos ORCID, C. Linhares Sales ORCID, K. Maia, N. Martins ORCID, R. Sampaio ORCID

    Journal reference : Volume 37, 2011, pp. 57-62

    DOI : 10.1016/j.endm.2011.05.011

  • On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

    Discrete Applied Mathematics

    Authors : B. Courcelle ORCID, J.A. Makowsky ORCID, U. Rotics

    Journal reference : Volume 108, 2001, pp. 23-52

    DOI : 10.1016/s0166-218x(00)00221-3

  • Total dominating sequences in trees, split graphs, and under modular decomposition

    Discrete Optimization

    Authors : Boštjan Brešar ORCID, Tim Kos, Graciela Nasini, Pablo Torres ORCID

    Journal reference : Volume 28, 2017, pp. 16-30

    DOI : 10.1016/j.disopt.2017.10.002

  • Graph classes with few P 4 ’s: Universality and Brownian graphon limits

    European Journal of Combinatorics

    Authors : Théo Lenoir

    Journal reference : Volume 134, 2026, pp. 104345

    DOI : 10.1016/j.ejc.2026.104345

  • On -sparse graphs and other families

    Electronic Notes in Discrete Mathematics

    Authors : Jean-Luc Fouquet, Jean-Marie Vanherpe

    Journal reference : Volume 17, 2004, pp. 163-167

    DOI : 10.1016/j.endm.2004.03.032

  • Restricted coloring problems on Graphs with few P 4’s

    Annals of Operations Research

    Authors : Cláudia Linhares-Sales ORCID, Ana Karolinna Maia ORCID, Nicolas Martins ORCID, Rudini M. Sampaio ORCID

    Journal reference : Volume 217, 2014, pp. 385-397

    DOI : 10.1007/s10479-014-1537-2

  • Counting Spanning Trees in Graphs Using Modular Decomposition

    Lecture notes in computer science

    Authors : Stavros D. Nikolopoulos ORCID, Leonidas Palios ORCID, Charis Papadopoulos ORCID

    Journal reference : Volume , 2011, pp. 202-213

    DOI : 10.1007/978-3-642-19094-0_21

  • On the Stress Transit Function

    Bulletin of the Iranian Mathematical Society.

    Authors : Arun Anil ORCID, Manoj Changat ORCID, Tanja Dravec ORCID, Jeny Jacob, Lekshmi Kamal K. Sheela ORCID, Iztok Peterin ORCID, Polona Repolusk, Rishi Ranjan Singh ORCID

    Journal reference : Volume 52, 2026, pp.

    DOI : 10.1007/s41980-025-01017-8

  • Hitting subgraphs in P4-tidy graphs

    Applied Mathematics and Computation

    Authors : Boštjan Brešar ORCID, Tim Kos, Rastislav Krivoš-Belluš, Gabriel Semanišin ORCID

    Journal reference : Volume 352, 2019, pp. 211-219

    DOI : 10.1016/j.amc.2019.01.074

  • The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs

    Electronic Notes in Discrete Mathematics

    Authors : M.P. Dobson, V. Leoni, G. Nasini

    Journal reference : Volume 36, 2010, pp. 559-566

    DOI : 10.1016/j.endm.2010.05.071

  • Bounding χ in terms of ω and Δ for some classes of graphs

    Discrete Mathematics

    Authors : N.R. Aravind, T. Karthick, C.R. Subramanian ORCID

    Journal reference : Volume 311, 2011, pp. 911-920

    DOI : 10.1016/j.disc.2011.02.021

  • Vizing Bound for the Chromatic Number on Some Graph Classes

    Graphs and Combinatorics

    Authors : T. Karthick, Frédéric Maffray ORCID

    Journal reference : Volume 32, 2015, pp. 1447-1460

    DOI : 10.1007/s00373-015-1651-1

  • Linear-time modular decomposition of directed graphs

    Discrete Applied Mathematics

    Authors : Ross M. McConnell, Fabien de Montgolfier ORCID

    Journal reference : Volume 145, 2004, pp. 198-209

    DOI : 10.1016/j.dam.2004.02.017

  • Bandwidth and topological bandwidth of graphs with few P4's

    Discrete Applied Mathematics

    Authors : Ton Kloks ORCID, Richard B. Tan

    Journal reference : Volume 115, 2001, pp. 117-133

    DOI : 10.1016/s0166-218x(01)00220-7

  • Counting spanning trees using modular decomposition

    Theoretical Computer Science

    Authors : Stavros D. Nikolopoulos ORCID, Leonidas Palios ORCID, Charis Papadopoulos ORCID

    Journal reference : Volume 526, 2014, pp. 41-57

    DOI : 10.1016/j.tcs.2014.01.012

  • χ -boundedness and related problems on graphs without long induced paths: A survey

    Discrete Applied Mathematics

    Authors : Arnab Char, T. Karthick

    Journal reference : Volume 364, 2024, pp. 99-119

    DOI : 10.1016/j.dam.2024.12.014

  • Structural characterizations of tree t-spanners for graphs with few P4’s and (0, ℓ)-graphs

    RAIRO - Operations Research

    Authors : Fernanda Couto ORCID, Luís Cunha, Diego Ferraz

    Journal reference : Volume 59, 2025, pp. 835-846

    DOI : 10.1051/ro/2025012

  • Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width

    Lecture notes in computer science

    Authors : B. Courcelle, J. A. Makowsky ORCID, U. Rotics

    Journal reference : Volume , 1998, pp. 1-16

    DOI : 10.1007/10692760_1

  • Clique-perfectness and balancedness of some graph classes

    Americanae (AECID Library)

    Authors : Flavia Bonomo ORCID, Guillermo Durán ORCID, Martín D. Safe ORCID, Annegret K. Wagler ORCID

    Journal reference : Volume 91, 2014, pp. 2118-2141

    DOI : 10.1080/00207160.2014.881994
Preview
Loading PDF preview...