A Short Proof of the Size of Edge-Extremal Chordal Graphs
Abstract
[3] have recently determined the maximum number of edges of a chordal graph with a maximum degree less than $d$ and the matching number at most $\nu$ by exhibiting a family of chordal graphs achieving this bound. We provide simple proof of their result.
Keywords
References
- [1] V. Chvatal, D. Hanson, Degrees and matchings, J. Comb. Theory., Ser. B, 20(2) (1976), 128–138.
- [2] N. Balachandran, N. Khare, Graphs with restricted valency and matching number, Discrete Mathematics, 309 (2009), 4176–4180.
- [3] J. R. S. Blair, P. Heggernes, P. T. Lima, D. Lokshtanov, On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number, Proceeding of the 14th Latin American Symposium on Theoretical Informatics (LATIN 2009), (2020), 600–612.
- [4] F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Comb. Theory., 16 (1974), 47–56.
- [5] T. Ekim, M. Shalom, O. S¸eker, The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation, J. Comb. Optim., 41(3) (2021), 710–735.
