Upload resources

Upload your works to SEDICI to increase its visibility and improve its impact


Show simple item record

dc.date.accessioned 2021-12-01T18:31:22Z
dc.date.available 2021-12-01T18:31:22Z
dc.date.issued 2020-01-28
dc.identifier.uri http://sedici.unlp.edu.ar/handle/10915/129017
dc.description.abstract 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. en
dc.format.extent 531-538 es
dc.language en es
dc.subject clique graph es
dc.subject clique-inverse graph es
dc.title On clique‐inverse graphs of graphs with bounded clique number en
dc.type Articulo es
sedici.identifier.other doi:10.1002/jgt.22544 es
sedici.identifier.issn 0364-9024 es
sedici.identifier.issn 1097-0118 es
sedici.creator.person Alcón, Liliana Graciela es
sedici.creator.person Gravier, Sylvain es
sedici.creator.person Linhares Sales, Cláudia es
sedici.creator.person Protti, Fábio es
sedici.creator.person Ravenna, Gabriela Susana es
sedici.subject.materias Matemática es
sedici.description.fulltext true es
mods.originInfo.place Facultad de Ciencias Exactas es
sedici.subtype Articulo es
sedici.rights.license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)
sedici.rights.uri http://creativecommons.org/licenses/by-nc-nd/4.0/
sedici.description.peerReview peer-review es
sedici.relation.journalTitle Journal of Graph Theory es
sedici.relation.journalVolumeAndIssue vol. 94, no. 4 es

Download Files

This item appears in the following Collection(s)

Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) Except where otherwise noted, this item's license is described as Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)