Sunil Chandran ; Vadim V. Lozin ; C.R. Subramanian - Graphs of low chordality

dmtcs:343 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, Vol. 7 - https://doi.org/10.46298/dmtcs.343
Graphs of low chordality

Authors: Sunil Chandran 1; Vadim V. Lozin 2; C.R. Subramanian 3

  • 1 Max-Planck-Institut für Informatik
  • 2 Rutgers Center for Operations Research
  • 3 Institute of Mathematical Sciences [Chennai]

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.

https://doi.org/10.46298/dmtcs.343
Source: HAL:hal-00959026v1
Volume: Vol. 7
Published on: January 1, 2005
Imported on: March 26, 2015
Keywords: induced cycles,chordality,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

6 Documents citing this article

Share and export

Consultation statistics

This page has been seen 214 times.
This article's PDF has been downloaded 184 times.