Clique-perfectness of complements of line graphs

Mostrar todas las versiones(2)

A graph is clique-perfect if the maximum number of pairwise disjoint maximal cliques equals the minimum number of vertices intersecting all maximal cliques for each induced subgraph. In this work, we give necessary and sufficient conditions for the complement of a line graph to be clique-perfect and...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K.
Formato: JOUR
Materias:
Clique-perfect graphs
Edge-coloring
Line graphs
Matchings
Graphic methods
All maximal cliques
Circular structures
Edge coloring
Induced subgraphs
Line graph
Perfect graph
Recognition algorithm
Graph theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0166218X_v186_n1_p19_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_0166218X_v186_n1_p19_Bonomo
record_format dspace
spelling todo:paper_0166218X_v186_n1_p19_Bonomo2023-10-03T15:03:43Z Clique-perfectness of complements of line graphs Bonomo, F. Durán, G. Safe, M.D. Wagler, A.K. Clique-perfect graphs Edge-coloring Line graphs Matchings Graphic methods All maximal cliques Circular structures Edge coloring Induced subgraphs Line graph Matchings Perfect graph Recognition algorithm Graph theory A graph is clique-perfect if the maximum number of pairwise disjoint maximal cliques equals the minimum number of vertices intersecting all maximal cliques for each induced subgraph. In this work, we give necessary and sufficient conditions for the complement of a line graph to be clique-perfect and an O (n2) -time algorithm to recognize such graphs. These results follow from a characterization and a linear-time recognition algorithm for matching-perfect graphs, which we introduce as graphs where the maximum number of pairwise edge-disjoint maximal matchings equals the minimum number of edges intersecting all maximal matchings for each subgraph. Thereby, we completely describe the linear and circular structure of the graphs containing no bipartite claw, from which we derive a structure theorem for all those graphs containing no bipartite claw that are Class 2 with respect to edge-coloring. © 2015 Elsevier B.V. All rights reserved. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0166218X_v186_n1_p19_Bonomo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Clique-perfect graphs
Edge-coloring
Line graphs
Matchings
Graphic methods
All maximal cliques
Circular structures
Edge coloring
Induced subgraphs
Line graph
Matchings
Perfect graph
Recognition algorithm
Graph theory
spellingShingle Clique-perfect graphs
Edge-coloring
Line graphs
Matchings
Graphic methods
All maximal cliques
Circular structures
Edge coloring
Induced subgraphs
Line graph
Matchings
Perfect graph
Recognition algorithm
Graph theory
Bonomo, F.
Durán, G.
Safe, M.D.
Wagler, A.K.
Clique-perfectness of complements of line graphs
topic_facet Clique-perfect graphs
Edge-coloring
Line graphs
Matchings
Graphic methods
All maximal cliques
Circular structures
Edge coloring
Induced subgraphs
Line graph
Matchings
Perfect graph
Recognition algorithm
Graph theory
description A graph is clique-perfect if the maximum number of pairwise disjoint maximal cliques equals the minimum number of vertices intersecting all maximal cliques for each induced subgraph. In this work, we give necessary and sufficient conditions for the complement of a line graph to be clique-perfect and an O (n2) -time algorithm to recognize such graphs. These results follow from a characterization and a linear-time recognition algorithm for matching-perfect graphs, which we introduce as graphs where the maximum number of pairwise edge-disjoint maximal matchings equals the minimum number of edges intersecting all maximal matchings for each subgraph. Thereby, we completely describe the linear and circular structure of the graphs containing no bipartite claw, from which we derive a structure theorem for all those graphs containing no bipartite claw that are Class 2 with respect to edge-coloring. © 2015 Elsevier B.V. All rights reserved.
format JOUR
author Bonomo, F.
Durán, G.
Safe, M.D.
Wagler, A.K.
author_facet Bonomo, F.
Durán, G.
Safe, M.D.
Wagler, A.K.
author_sort Bonomo, F.
title Clique-perfectness of complements of line graphs
title_short Clique-perfectness of complements of line graphs
title_full Clique-perfectness of complements of line graphs
title_fullStr Clique-perfectness of complements of line graphs
title_full_unstemmed Clique-perfectness of complements of line graphs
title_sort clique-perfectness of complements of line graphs
url http://hdl.handle.net/20.500.12110/paper_0166218X_v186_n1_p19_Bonomo
work_keys_str_mv AT bonomof cliqueperfectnessofcomplementsoflinegraphs
AT durang cliqueperfectnessofcomplementsoflinegraphs
AT safemd cliqueperfectnessofcomplementsoflinegraphs
AT waglerak cliqueperfectnessofcomplementsoflinegraphs
_version_ 1807315518405738496

Ejemplares similares