Premium
On clique‐inverse graphs of graphs with bounded clique number
Author(s) -
Alcón Liliana,
Gravier Sylvain,
Sales Claudia L.,
Protti Fabio,
Ravenna Gabriela
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22544
Subject(s) - combinatorics , mathematics , split graph , chordal graph , clique graph , discrete mathematics , clique sum , block graph , treewidth , cograph , clique problem , graph , pathwidth , 1 planar graph , line graph , graph power
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 asK − 1( F ) = { H | K ( H ) ∈ F } . Let F p be the family of K p ‐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( F p ) 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( F p ) 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( F p ) in terms of p .