On the helly defect of a graph

AUTOR(ES)

Dourado, Mitre C., Protti, Fábio, Szwarcfiter, Jayme L.

FONTE

Journal of the Brazilian Computer Society

DATA DE PUBLICAÇÃO

2001

RESUMO

The Helly defect of a graph G is the smallest integer i such that the iterated clique graph Ki(G) is clique-Kelly. We prove that it is NP-hard to decide whether the Helly defect of G is at most 1.

Documentos Relacionados

• Helly property, clique graphs, complementary graph classes, and sandwich problems
• On a conjecture concerning helly circle graphs
• A Note on the Matching Polytope of a Graph
• Computational aspects of the Helly property: a survey
• On the homotopy type of the clique graph