Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Graphs of low chorda ...
Article

Graphs of low chordality

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]
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2005
Last modified on
March 31, 2025
Volume 7
vol. 7
DOI
10.46298/dmtcs.343
License
https://about.hal.science/hal-authorisation-v1
Indicators
989
Views
1761
Downloads

Graphs of low chordality

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]
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • induced cycles
  • chordality
Cited by

Source: OpenCitations

  • An improved algorithm for the longest induced path problem on k -chordal graphs

    Discrete Applied Mathematics

    Authors : Tetsuya Ishizeki, Yota Otachi ORCID, Koichi Yamazaki ORCID

    Journal reference : Volume 156, 2008, pp. 3057-3059

    DOI : 10.1016/j.dam.2008.01.019

  • Partitioning the vertices of a cubic graph into two total dominating sets

    Discrete Applied Mathematics

    Authors : Wyatt J. Desormeaux, Teresa W. Haynes ORCID, Michael A. Henning ORCID

    Journal reference : Volume 223, 2017, pp. 52-63

    DOI : 10.1016/j.dam.2017.01.032

  • Many toric ideals generated by quadratic binomials possess no quadratic Gröbner bases

    Journal of Algebra

    Authors : Takayuki Hibi ORCID, Kenta Nishiyama, Hidefumi Ohsugi ORCID, Akihiro Shikama ORCID

    Journal reference : Volume 408, 2013, pp. 138-146

    DOI : 10.1016/j.jalgebra.2013.09.039

  • Induced 2-regular subgraphs in k -chordal cubic graphs

    Discrete Applied Mathematics

    Authors : Michael A. Henning ORCID, F. Joos ORCID, C. Löwenstein, D. Rautenbach ORCID

    Journal reference : Volume 205, 2016, pp. 73-79

    DOI : 10.1016/j.dam.2016.01.009

  • A Dirac-type characterization of k -chordal graphs

    Discrete Mathematics

    Authors : R. Krithika ORCID, Rogers Mathew ORCID, N.S. Narayanaswamy, N. Sadagopan

    Journal reference : Volume 313, 2013, pp. 2865-2867

    DOI : 10.1016/j.disc.2013.08.032

  • Metric Dimension of Bounded Tree-length Graphs

    SIAM Journal on Discrete Mathematics

    Authors : Rémy Belmonte ORCID, Fedor V. Fomin ORCID, Petr A. Golovach ORCID, M. S. Ramanujan

    Journal reference : Volume 31, 2017, pp. 1217-1243

    DOI : 10.1137/16m1057383

  • Inductive graph invariants and approximation algorithms

    Discrete Mathematics Algorithms and Applications

    Authors : C. R. Subramanian ORCID

    Journal reference : Volume 14, 2021, pp.

    DOI : 10.1142/s1793830922500197

  • Generalized Metric Repair on Graphs

    DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Authors : Fan, Gilbert, Raichel, Sonthalia, Van Buskirk

    Journal reference : Volume 162, 2020, pp. 22

    DOI : 10.4230/lipics.swat.2020.25
Preview
Loading PDF preview...