On clique‐inverse graphs of graphs with bounded clique number
The clique graph K(G) of G is the intersection graph of the family of maximal cliques of G. For a family F of graphs, the family of clique-inverse graphs of F, denoted by K−1(F), is defined as K−1(F) = {H|K(H) ∈ F}. Let F p be the family of Kp-free graphs, that is, graphs with clique number at most...
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Articulo |
| Lenguaje: | Inglés |
| Publicado: |
2020
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/129017 |
| Aporte de: |
| id |
I19-R120-10915-129017 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Inglés |
| topic |
Matemática clique graph clique-inverse graph |
| spellingShingle |
Matemática clique graph clique-inverse graph Alcón, Liliana Graciela Gravier, Sylvain Linhares Sales, Cláudia Protti, Fábio Ravenna, Gabriela Susana On clique‐inverse graphs of graphs with bounded clique number |
| topic_facet |
Matemática clique graph clique-inverse graph |
| description |
The clique graph K(G) of G is the intersection graph of the family of maximal cliques of G. For a family F of graphs, the family of clique-inverse graphs of F, denoted by K−1(F), is defined as K−1(F) = {H|K(H) ∈ F}. Let F p be the family of Kp-free graphs, that is, graphs with clique number at most p − 1, for an integer constant p ≥ 2. Deciding whether a graph H is a clique-inverse graph of F p can be done in polynomial time; in addition, for p ∈ {2, 3, 4}, K − 1 (Fp) can be characterized by a finite family of forbidden induced subgraphs. In Protti and Szwarcfiter, the authors propose to extend such characterizations to higher values of p. Then a natural question arises: Is there a characterization of K − 1 (Fp) by means of a finite family of forbidden induced subgraphs, for any p ≥ 2? In this note we give a positive answer to this question. We present upper bounds for the order, the clique number, and the stability number of every forbidden induced subgraph for K − 1 (Fp) in terms of p. |
| format |
Articulo Articulo |
| author |
Alcón, Liliana Graciela Gravier, Sylvain Linhares Sales, Cláudia Protti, Fábio Ravenna, Gabriela Susana |
| author_facet |
Alcón, Liliana Graciela Gravier, Sylvain Linhares Sales, Cláudia Protti, Fábio Ravenna, Gabriela Susana |
| author_sort |
Alcón, Liliana Graciela |
| title |
On clique‐inverse graphs of graphs with bounded clique number |
| title_short |
On clique‐inverse graphs of graphs with bounded clique number |
| title_full |
On clique‐inverse graphs of graphs with bounded clique number |
| title_fullStr |
On clique‐inverse graphs of graphs with bounded clique number |
| title_full_unstemmed |
On clique‐inverse graphs of graphs with bounded clique number |
| title_sort |
on clique‐inverse graphs of graphs with bounded clique number |
| publishDate |
2020 |
| url |
http://sedici.unlp.edu.ar/handle/10915/129017 |
| work_keys_str_mv |
AT alconlilianagraciela oncliqueinversegraphsofgraphswithboundedcliquenumber AT graviersylvain oncliqueinversegraphsofgraphswithboundedcliquenumber AT linharessalesclaudia oncliqueinversegraphsofgraphswithboundedcliquenumber AT prottifabio oncliqueinversegraphsofgraphswithboundedcliquenumber AT ravennagabrielasusana oncliqueinversegraphsofgraphswithboundedcliquenumber |
| bdutipo_str |
Repositorios |
| _version_ |
1764820451778887683 |