Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-00959026
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Thursday, June 12, 2014 - 10:54:31 AM
Last modification on : Monday, August 19, 2019 - 4:20:06 PM
Long-term archiving on: : Friday, September 12, 2014 - 10:36:35 AM

File

59-75-1-PB.pdf
Explicit agreement for this submission

Identifiers

Collections

Citation

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

Share

Metrics

Record views

126

Files downloads

674