On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number
- Jean Blair,
- Pinar Heggernes,
- ,
- Daniel Lokshtanov
- United States Military Academy,
- University of Bergen,
- ,
- University of California
Research Output:
Journal Article or Conference Article in Journal
Journal article
Peer-reviewOpen access
Publication Information
Output type
Research Output:
Journal Article or Conference Article in Journal
Journal article
Peer-reviewOriginal language
EnglishJournal (Volume, Issue Number)
AlgorithmicaPublication milestones
- Published - 2022
Publication status
Published - 2022
ISSN
0178-4617Publication IDs
- Scopus: 85126845996
Abstract
We determine the maximum number of edges that a chordal
graph G can have if its degree, ∆(G), and its matching number, ν(G), are bounded. To do so, we show that for every d, ν ∈ N, there exists a chordal graph G with ∆(G) < d and ν(G) < ν whose number of edges matches the upper bound, while having a simple structure: it is a disjoint union of cliques and stars.
graph G can have if its degree, ∆(G), and its matching number, ν(G), are bounded. To do so, we show that for every d, ν ∈ N, there exists a chordal graph G with ∆(G) < d and ν(G) < ν whose number of edges matches the upper bound, while having a simple structure: it is a disjoint union of cliques and stars.
Publication metrics
PlumX, opens in new tab
Citations
3
Captures
2
Access to documents
Final published version
Final published version, 611.87 KB
