{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T06:38:44Z","timestamp":1769755124535,"version":"3.49.0"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2022,3,22]],"date-time":"2022-03-22T00:00:00Z","timestamp":1647907200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,3,22]],"date-time":"2022-03-22T00:00:00Z","timestamp":1647907200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["CLASSIS"],"award-info":[{"award-number":["CLASSIS"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s00453-022-00953-9","type":"journal-article","created":{"date-parts":[[2022,3,22]],"date-time":"2022-03-22T11:03:33Z","timestamp":1647947013000},"page":"3587-3602","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number"],"prefix":"10.1007","volume":"84","author":[{"given":"Jean R. S.","family":"Blair","sequence":"first","affiliation":[]},{"given":"Pinar","family":"Heggernes","sequence":"additional","affiliation":[]},{"given":"Paloma T.","family":"Lima","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,22]]},"reference":[{"key":"953_CR1","doi-asserted-by":"publisher","first-page":"4176","DOI":"10.1016\/j.disc.2008.10.007","volume":"309","author":"N Balachandran","year":"2009","unstructured":"Balachandran, N., Khare, N.: Graphs with restricted valency and matching number. Discr. Math. 309, 4176\u20134180 (2009)","journal-title":"Discr. Math."},{"key":"953_CR2","doi-asserted-by":"crossref","unstructured":"Belmonte, R., Heggernes, P., van\u00a0\u2019t Hof, P., Saei, R.: Ramsey numbers for line graphs and perfect graphs. In: Proceedings of COCOON 2012, pp. 204\u2013215 (2012)","DOI":"10.1007\/978-3-642-32241-9_18"},{"key":"953_CR3","doi-asserted-by":"crossref","unstructured":"Blair, J.R.S., Heggernes, P., Lima, P.T., Lokshtanov, D.: On the maximum number of edges in chordal graphs of bounded degree and matching number. In: Proceedings of LATIN 2020, pp. 600\u2013612 (2020)","DOI":"10.1007\/978-3-030-61792-9_47"},{"key":"953_CR4","first-page":"1","volume-title":"Graph Theory and Sparse Matrix Computation","author":"JRS Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: Graph Theory and Sparse Matrix Computation, pp. 1\u201329. Springer, New York (1993)"},{"key":"953_CR5","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s00373-018-1986-5","volume":"35","author":"Y Cao","year":"2019","unstructured":"Cao, Y., Chen, G., Jing, G., Stiebitz, M., Toft, B.: Graph edge coloring: a survey. Graphs Comb. 35, 33\u201366 (2019)","journal-title":"Graphs Comb."},{"key":"953_CR6","first-page":"137","volume":"17","author":"B Chen","year":"1995","unstructured":"Chen, B., Fu, H., Ko, M.: Total chromatic number and chromatic index of split graphs. J. Comb. Math. Comb. Comput. 17, 137\u2013146 (1995)","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"953_CR7","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/0095-8956(76)90004-6","volume":"20","author":"V Chv\u00e1tal","year":"1976","unstructured":"Chv\u00e1tal, V., Hanson, D.: Degrees and matchings. J. Comb. Theory Series B 20, 128\u2013138 (1976)","journal-title":"J. Comb. Theory Series B"},{"key":"953_CR8","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1016\/j.disc.2017.01.010","volume":"340","author":"C Dibek","year":"2017","unstructured":"Dibek, C., Ekim, T., Heggernes, P.: Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded. Discr. Math. 340, 927\u2013934 (2017)","journal-title":"Discr. Math."},{"key":"953_CR9","first-page":"79","volume":"32","author":"CMH de Figueiredo","year":"2000","unstructured":"de Figueiredo, C.M.H., Meidanis, J., de Mello, C.P.: Local conditions for edge-colouring. J. Comb. Math. Comb. Comput. 32, 79\u201391 (2000)","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"953_CR10","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific J. Math. 15, 835\u2013855 (1965)","journal-title":"Pacific J. Math."},{"key":"953_CR11","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Series B 16, 47\u201356 (1974)","journal-title":"J. Comb. Theory Series B"},{"key":"953_CR12","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-colouring. SIAM J. Comput. 10, 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"953_CR13","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1006\/jctb.1996.0032","volume":"67","author":"M Kochol","year":"1996","unstructured":"Kochol, M.: Snarks without small cycles. J. Comb. Theory Series B 67, 34\u201347 (1996)","journal-title":"J. Comb. Theory Series B"},{"key":"953_CR14","unstructured":"M\u00e5land, E.: Maximum number of edges in graph classes under degree and matching constraints. Master\u2019s thesis, University of Bergen, Norway (2015)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00953-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00953-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00953-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T12:11:44Z","timestamp":1669637504000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00953-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,22]]},"references-count":14,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["953"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00953-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,22]]},"assertion":[{"value":"18 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}