Graphs of low chordality - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2005

Graphs of low chordality

Résumé

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.

Mots clés

Fichier principal
Vignette du fichier
59-75-1-PB.pdf (83.33 Ko) Télécharger le fichier
Origine : Accord explicite pour ce dépôt
Loading...

Dates et versions

hal-00959026 , version 1 (12-06-2014)

Identifiants

Citer

Sunil L. Chandran, Vadim V. Lozin, C.R. Subramanian. Graphs of low chordality. Discrete Mathematics and Theoretical Computer Science, 2005, Vol. 7, pp.25-36. ⟨10.46298/dmtcs.343⟩. ⟨hal-00959026⟩

Collections

TDS-MACS
133 Consultations
855 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More