Graphs of low chordality

Abstract : The chordality of a graph with at least one cycle is the length of the longest induced cycle in it. The odd (even) chordality is defined to be the length of the longest induced odd (even) cycle in it. Chordal graphs have chordality at most 3. We show that co-circular-arc graphs and co-circle graphs have even chordality at most 4. We also identify few other classes of graphs having bounded (by a constant) chordality values.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2005, 7, pp.25-36
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00959026
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 12 juin 2014 - 10:54:31
Dernière modification le : mardi 21 novembre 2017 - 01:06:57
Document(s) archivé(s) le : vendredi 12 septembre 2014 - 10:36:35

Fichier

59-75-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-00959026, version 1

Collections

Citation

Sunil Chandran, Vadim V. Lozin, C.R. Subramanian. Graphs of low chordality. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2005, 7, pp.25-36. 〈hal-00959026〉

Partager

Métriques

Consultations de la notice

148

Téléchargements de fichiers

164