Contents

Ars Combinatoria

  • Research article

Extreme Cliques in Interval Graphs

Marcia R.Cerioli1, Fabiano de S.Oliveira2, Jayme L.Szwarcfiter3
1Universidade Federal do Rio de Janeiro – Instituto de Matematica and COPPE, Caixa Postal 68530, 21945-970, Rio de Janeiro, RJ, Brasil.
2Universidade Federal do Rio de Janeiro – COPPE, Brasil.
3Universidade Federal do Rio de Janeiro – Instituto de Matematica, NCE, and COPPE, Brasil.
  • Published: 31/01/2010

Abstract

A clique \(C\) is an extreme clique of an interval graph \(G\) if there exists some interval model of \(G\) in which \(C\) is the first clique. A graph \(G\) is homogeneously clique-representable if all cliques of \(G\) are extreme cliques. In this paper, we present characterizations of extreme cliques and homogeneously clique-representable graphs.

Information
Guidelines
CP Initiatives
Follow CP
Facebook X-twitter Linkedin

1970-2025 CP (Manitoba, Canada) unless otherwise stated.

Citation
Marcia R.Cerioli, Fabiano de S.Oliveira, Jayme L.Szwarcfiter. Extreme Cliques in Interval Graphs[J], Ars Combinatoria, Volume 094. 103-114. .