On the maximum number of edges in chordal graphs of bounded degree and matching number

DOI10.1007/S00453-022-00953-9MaRDI QIDQ5970781zbMATH OpenOpenAlexFDO

Authors Jean R. S. Blair, Pinar Heggernes, Paloma T. Lima, Daniel Lokshtanov

Publication date 8 December 2022

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-022-00953-9

zbMATH Keywords

chordal graphsmatching numbermaximum number of edges

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Recommendations

• On the maximum number of edges in chordal graphs of bounded degree and matching number
• On the maximum number of edges in planar graphs of bounded degree and matching number
• On the maximum number of edges in a hypergraph with given matching number
• Lower bounds on the number of edges in edge-chromatic-critical graphs with fixed maximum degrees
• Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded
• Tight lower bounds on the matching number in a graph with given maximum degree
• scientific article; zbMATH DE number 1409205
• Bounding the number of edges of matchstick graphs
• Matching and edge-connectivity in graphs with given maximum degree
• On the maximum number of edges in hypergraphs with fixed matching and clique number

Cites work

• Degrees and matchings
• Graph edge coloring: a survey
• Graphs with restricted valency and matching number
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 1463393 (Why is no real title available?)
• scientific article; zbMATH DE number 749267 (Why is no real title available?)
• Incidence matrices and interval graphs
• Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded
• On the maximum number of edges in chordal graphs of bounded degree and matching number
• Ramsey numbers for line graphs and perfect graphs
• Snarks without small cycles
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The NP-Completeness of Edge-Coloring

Cited in

(4)

• On the maximum number of edges in chordal graphs of bounded degree and matching number
• On the maximum number of edges in planar graphs of bounded degree and matching number
• Maximum size of connected graphs with bounded maximum degree and matching number
• Constructing extremal triangle-free graphs using integer programming

This page was built for publication: On the maximum number of edges in chordal graphs of bounded degree and matching number

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