On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number

Jean Blair; Pinar Heggernes; Paloma Thomé de Lima; Daniel Lokshtanov

doi:10.1007/s00453-022-00953-9

On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number

Jean Blair, Pinar Heggernes, Paloma Thomé de Lima, Daniel Lokshtanov

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

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.

Originalsprog	Engelsk
Tidsskrift	Algorithmica
ISSN	0178-4617
DOI	https://doi.org/10.1007/s00453-022-00953-9
Status	Udgivet - 2022

Adgang til dokumentet

10.1007/s00453-022-00953-9

maxEdgesChordalWG20Forlagets udgivne version, 612 KB

https://sites.cs.ucsb.edu/~daniello/papers/maxEdgesChordalWG20.pdf

Citationsformater

@article{50d364c046374f5cba3065fda08601e3,

title = "On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number",

abstract = "We determine the maximum number of edges that a chordalgraph 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.",

keywords = "Chordal graphs, Maximum number of edges, Matching number",

author = "Jean Blair and Pinar Heggernes and {Thom{\'e} de Lima}, Paloma and Daniel Lokshtanov",

year = "2022",

doi = "10.1007/s00453-022-00953-9",

language = "English",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York LLC",

}

TY - JOUR

T1 - On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number

AU - Blair, Jean

AU - Heggernes, Pinar

AU - Thomé de Lima, Paloma

AU - Lokshtanov, Daniel

PY - 2022

Y1 - 2022

N2 - We determine the maximum number of edges that a chordalgraph 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.

AB - We determine the maximum number of edges that a chordalgraph 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.

KW - Chordal graphs

KW - Maximum number of edges

KW - Matching number

U2 - 10.1007/s00453-022-00953-9

DO - 10.1007/s00453-022-00953-9

M3 - Journal article

SN - 0178-4617

JO - Algorithmica

JF - Algorithmica

ER -

On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater