A Dirac-type characterization of k-chordal graphs

DOI10.1016/J.DISC.2013.08.032zbMATH Open1281.05082arXiv1206.5397OpenAlexW2122599841MaRDI QIDQ394280FDOQ394280

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

Publication date: 27 January 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Characterization of k-chordal graphs based on the existence of a "simplicial path" was shown in [Chv{'a}tal et al. Note: Dirac-type characterizations of graphs without long chordless cycles. Discrete Mathematics, 256, 445-448, 2002]. We give a characterization of k-chordal graphs which is a generalization of the known characterization of chordal graphs due to [G. A. Dirac. On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg, 25, 71-76, 1961] that use notions of a "simplicial vertex" and a "simplicial ordering".

Full work available at URL: https://arxiv.org/abs/1206.5397

Recommendations

• Dirac-type characterizations of graphs without long chordless cycles
• A \(k\)-partite generalization of chordal bipartite graphs
• Characterizing k-chordal unichord-free graphs
• A characterization of strongly chordal graphs
• scientific article; zbMATH DE number 1011066

zbMATH Keywords

simplicial vertexcharacterization\(k\)-chordal graphssimplicial ordering

Mathematics Subject Classification ID

Paths and cycles (05C38)

Cites Work

• Treewidth for graphs with small chordality
• Dirac-type characterizations of graphs without long chordless cycles
• Algorithmic graph theory and perfect graphs
• Incidence matrices and interval graphs
• Title not available (Why is that?)
• On rigid circuit graphs
• Finding large holes

Cited In (19)

• Induced 2-regular subgraphs in \(k\)-chordal cubic graphs
• Characterizing k-chordal unichord-free graphs
• The graphs that Dahlhaus called ``good generalized strongly chordal
• Generalized chordality, vertex separators and hyperbolicity on graphs
• Partitioning the vertices of a cubic graph into two total dominating sets
• On strictly chordality-\(k\) graphs
• Dirac-type characterizations of graphs without long chordless cycles
• An inequality characterizing chordal graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Avoidable vertices and edges in graphs: existence, characterization, and applications
• Graphs that have separator tree representations
• Fuzzy chordal graphs and its properties
• Some results on connected vertex separators
• Title not available (Why is that?)
• Dirac's theorem on simplicial matroids
• Title not available (Why is that?)
• Dirac's theorem on chordal graphs and Alexander duality
• Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs

This page was built for publication: A Dirac-type characterization of \(k\)-chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q394280)