Coordinated graphs and clique graphs of clique-Helly perfect graphs
2007, Utilitas Mathematica 72, 175-192, 2007Citas: 19
Agregar PDF Plots Conexiones
Autor(es)
Flavia Bonomo and Guillermo Durán and Marina Groshaus
Abstract
A new class of graphs related to perfect graphs is defined in this work: coordinated graphs. A graph G is coordinated if the cardinality of a maximum set of cliques of H with a common vertex is equal to the cardinality of a minimum partition of the cliques of H into cliqueindependent sets, for every induced subgraph H of G. A graph G is K-perfect when its clique graph K (G) is perfect. The concept of special clique subgraph is defined, which leads us to the notion of c-coordinated graphs (coordination relative to these clique subgraphs). We prove that coordinated graphs are a subclass of perfect graphs and relate K-perfect graphs with c-coordinated graphs. Finally, clique graphs of clique-Helly and hereditary clique-Helly perfect graphs are analyzed.
Plot de citas
Citas
| # | Title | Year | Source | Authors | |
|---|---|---|---|---|---|
| 1 | NP-completeness results for edge modification problems | 2006 | Discrete Applied Mathematics | P Burzyn, F Bonomo, G Durán | |
| 2 | On clique-perfect and K-perfect graphs | 2006 | Ars combinatoria | F Bonomo, G Durán, M Groshaus, JL Szwarcfiter | |
| 3 | Bicliques, cliques, neighborhoods y la propiedad de Helly | 2006 | NA | ME Groshaus | |
| 4 | NP-hardness of the recognition of coordinated graphs | 2009 | Annals of Operations Research | FJ Soulignac, G Sueiro | |
| 5 | Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs | 2009 | Discrete applied mathematics | F Bonomo, G Durán, F Soulignac, G Sueiro | |
| 6 | Structural Similarity of Objects Represented by Ordinary Graphs | 2023 | Automatic Documentation and Mathematical … | SM Gusakova | |
| 7 | On some graph classes related to perfect graphs: A survey | 2020 | Discrete Applied … | F Bonomo-Braberman, G Durán, MD Safe | |
| 8 | Exponential families of minimally non-coordinated graphs | 2009 | Revista de la Unión Matemática … | F Soulignac, G Sueiro | |
| 9 | Partial characterizations of coordinated graphs: line graphs and complements of forests | 2009 | Mathematical Methods of … | F Bonomo, G Durán, F Soulignac, G Sueiro | |
| 10 | Edge contraction and edge removal on iterated clique graphs | 2013 | Discrete Applied … | ME Frías-Armenta, F Larrión, V Neumann-Lara | |
| 11 | Iterated clique graphs and bordered compact surfaces | 2013 | Discrete Mathematics | F Larrión, MA Pizaña, R Villarroel-Flores | |
| 12 | Balancedness of subclasses of circular-arc graphs | 2014 | Discrete Mathematics & … | F Bonomo, G Durán, MD Safe | |
| 13 | Neighborhood covering and independence on -tidy graphs and tree-cographs | 2020 | Annals of Operations Research | G Durán, M Safe, X Warnes | |
| 14 | Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs | 2008 | Electronic Notes in Discrete … | F Bonomo, G Durán, F Soulignac, G Sueiro | |
| 15 | On the clique behavior of circulants with three small jumps | 2009 | Electronic Notes in Discrete … | F Larrión, MA Pizaña, R Villarroel-Flores | |
| 16 | Neighborhood covering and independence on two superclasses of cographs | 2016 | arXiv preprint arXiv:1601.00032 | G Durán, MD Safe, XS Warnes | |
| 17 | Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey | 2013 | Electronic Notes in Discrete Mathematics | G Durán | |
| 18 | Sobre la coordinación de los complementos de lınea de árboles | NA | NA | RBS Albanesi | |
| 19 | Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König | 2011 | NA | MD Safe | |
| 20 | Un estado del arte acerca de grafos perfectos y algunas variaciones | 2015 | NA | N Pardal |
Citas de Scrapping
| # | Año | #Citas | Título | Autores | Journal | Editor |
|---|---|---|---|---|---|---|
| 1 | 2006 | 101 | NP-completeness results for edge modification problems | P Burzyn, F Bonomo, G Durán | Discrete Applied Mathematics, 2006 | Elsevier |
| 2 | 2006 | 33 | On clique-perfect and K-perfect graphs | F Bonomo, G Durán, M Groshaus, JL Szwarcfiter | Ars combinatoria, 2006 | mate.dm.uba.ar |
| 3 | 2006 | 11 | Bicliques, cliques, neighborhoods y la propiedad de Helly | ME Groshaus | 2006 | bibliotecadigital.exactas.uba.ar |
| 4 | 2009 | 12 | NP-hardness of the recognition of coordinated graphs | FJ Soulignac, G Sueiro | Annals of Operations Research, 2009 | Springer |
| 5 | 2009 | 12 | Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs | F Bonomo, G Durán, F Soulignac, G Sueiro | Discrete applied mathematics, 2009 | Elsevier |
| 6 | 2023 | 2 | Structural Similarity of Objects Represented by Ordinary Graphs | SM Gusakova | Automatic Documentation and Mathematical …, 2023 | Springer |
| 7 | 2020 | 13 | On some graph classes related to perfect graphs: A survey | F Bonomo-Braberman, G Durán, MD Safe… | Discrete Applied …, 2020 | Elsevier |
| 8 | 2009 | 8 | Exponential families of minimally non-coordinated graphs | F Soulignac, G Sueiro | Revista de la Unión Matemática …, 2009 | SciELO Argentina |
| 9 | 2009 | 9 | Partial characterizations of coordinated graphs: line graphs and complements of forests | F Bonomo, G Durán, F Soulignac, G Sueiro | Mathematical Methods of …, 2009 | Springer |
| 10 | 2013 | 4 | Edge contraction and edge removal on iterated clique graphs | ME Frías-Armenta, F Larrión, V Neumann-Lara… | Discrete Applied …, 2013 | Elsevier |
| 11 | 2013 | 4 | Iterated clique graphs and bordered compact surfaces | F Larrión, MA Pizaña, R Villarroel-Flores | Discrete Mathematics, 2013 | Elsevier |
| 12 | 2014 | 3 | Balancedness of subclasses of circular-arc graphs | F Bonomo, G Durán, MD Safe… | Discrete Mathematics & …, 2014 | dmtcs.episciences.org |
| 13 | 2020 | 2 | Neighborhood covering and independence on -tidy graphs and tree-cographs | G Durán, M Safe, X Warnes | Annals of Operations Research, 2020 | Springer |
| 14 | 2008 | 2 | Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs | F Bonomo, G Durán, F Soulignac, G Sueiro | Electronic Notes in Discrete …, 2008 | Elsevier |
| 15 | 2009 | 1 | On the clique behavior of circulants with three small jumps | F Larrión, MA Pizaña, R Villarroel-Flores | Electronic Notes in Discrete …, 2009 | Elsevier |
| 16 | 1601 | 0 | Neighborhood covering and independence on two superclasses of cographs | G Durán, MD Safe, XS Warnes | arXiv preprint arXiv:1601.00032, 2016 | arxiv.org |
| 17 | 2013 | 0 | Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey | G Durán | Electronic Notes in Discrete Mathematics, 2013 | Elsevier |
| 18 | 0 | Sobre la coordinación de los complementos de lınea de árboles | RBS Albanesi | union-matematica.org.ar | ||
| 19 | 2011 | 1 | Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König | MD Safe | 2011 | bibliotecadigital.exactas.uba.ar |
| 20 | 2015 | 0 | Un estado del arte acerca de grafos perfectos y algunas variaciones | N Pardal | 2015 | cms.dm.uba.ar |