Discrete Mathematics & Theoretical Computer Science, Vol 7 (2005)

Font Size:  Small  Medium  Large

Graphs of low chordality

L. Sunil Chandran, Vadim V. Lozin, C. R. Subramanian


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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page