{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T08:24:20Z","timestamp":1764059060497,"version":"3.45.0"},"reference-count":32,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T00:00:00Z","timestamp":1761350400000},"content-version":"vor","delay-in-days":297,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Procedia Computer Science"],"published-print":{"date-parts":[[2025]]},"DOI":"10.1016\/j.procs.2025.10.281","type":"journal-article","created":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T08:19:08Z","timestamp":1764058748000},"page":"62-69","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Lower Bounds for Induced-Universal Graphs"],"prefix":"10.1016","volume":"273","author":[{"given":"Cyril","family":"Gavoille","sequence":"first","affiliation":[]},{"given":"Amaury","family":"Jacques","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.procs.2025.10.281_bib1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00039-017-0396-9","article-title":"Asymptotically optimal induced universal graphs","volume":"27","author":"Alon","year":"2017","journal-title":"Geometric and Functional Analysis"},{"key":"10.1016\/j.procs.2025.10.281_bib2","doi-asserted-by":"crossref","unstructured":"Alon, N., Seymour, P.D., Thomas, R., 1990. A separator theorem for graphs with an excluded minor and its applications, in: 22nd Annual ACM Symp. on Theory of Computing (STOC), ACM Press. pp. 293\u2013299. doi: 10.1145\/100216.100254.","DOI":"10.1145\/100216.100254"},{"key":"10.1016\/j.procs.2025.10.281_bib3","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Dahlgaard, S., B\u00e6k Tejs Knudsen, M., 2017. Optimal induced universal graphs and adjacency labeling for trees. J. of the ACM 64, No. 27, pp. 1\u201322. doi: 10.1145\/3088513.","DOI":"10.1145\/3088513"},{"key":"10.1016\/j.procs.2025.10.281_bib4","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1137\/16M1105967","article-title":"Adjacency labeling schemes and induced-universal graphs","volume":"33","author":"Alstrup","year":"2019","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"10.1016\/j.procs.2025.10.281_bib5","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Fusy, \u00c9., Kang, M., Vigerske, S., 2007a. Enumeration and asymptotic properties of unlabeled outerplanar graphs. Electronic J. of Combinatorics 14, #R66.","DOI":"10.37236\/984"},{"key":"10.1016\/j.procs.2025.10.281_bib6","doi-asserted-by":"crossref","first-page":"2091","DOI":"10.1016\/j.ejc.2007.04.011","article-title":"Enumeration and limit laws for series-parallel graphs","volume":"28","author":"Bodirsky","year":"2007","journal-title":"European J. of Combinatorics"},{"key":"10.1016\/j.procs.2025.10.281_bib7","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.comgeo.2006.05.006","article-title":"On simultaneous planar graph embeddings","volume":"36","author":"Brass","year":"2007","journal-title":"Computational Geometry"},{"key":"10.1016\/j.procs.2025.10.281_bib8","doi-asserted-by":"crossref","first-page":"1334","DOI":"10.1109\/18.59932","article-title":"A new table of constant weight codes","volume":"36","author":"Brouwer","year":"1990","journal-title":"IEEE Transactions on Information Theory"},{"key":"10.1016\/j.procs.2025.10.281_bib9","doi-asserted-by":"crossref","unstructured":"Colbrun, C.J., Dinitz, J.H., 2007. Handbook of Combinatorial Designs. Disc. Math. and its Applications, Chapman and Hall\/CRC. doi: 10.1201\/9781420010541.","DOI":"10.1201\/9781420010541"},{"key":"10.1016\/j.procs.2025.10.281_bib10","doi-asserted-by":"crossref","unstructured":"Dujmovi\u0107, V., Esperet, L., Gavoille, C., Joret, G., Micek, P., Morin, P., 2021. Adjacency labelling for planar graphs (and beyond). J. of the ACM 68, No. 42, pp. 1\u201333. doi: 10.1145\/3477542.","DOI":"10.1145\/3477542"},{"key":"10.1016\/j.procs.2025.10.281_bib11","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.ipl.2008.04.020","article-title":"On induced-universal graphs for the class of bounded-degree graphs","volume":"108","author":"Esperet","year":"2008","journal-title":"Information Processing Letters"},{"key":"10.1016\/j.procs.2025.10.281_bib12","unstructured":"Gavoille, C., Hilaire, C., 2023. Minor-Universal Graph for Graphs on Surfaces. Technical Report 2305.06673v1 [cs.DM]. arXiv. doi: 10.48550\/arXiv.2305.06673."},{"key":"10.1016\/j.procs.2025.10.281_bib13","unstructured":"Gavoille, C., Jacques, A., 2025. Lower Bounds for Induced-Universal Graphs. Technical Report 2508.11585v1 [math.CO]. arXiv. URL:http:\/\/arxiv.org\/abs\/2508.11585."},{"key":"10.1016\/j.procs.2025.10.281_bib14","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Janczewski, W., 2022. Simpler adjacency labeling for planar graphs with B-trees, in: 25th Symp. on Simplicity in Algorithms (SOSA), ACM-SIAM. pp. 24\u201336. doi: 10.1137\/1.9781611977066.3.","DOI":"10.1137\/1.9781611977066.3"},{"key":"10.1016\/j.procs.2025.10.281_bib15","doi-asserted-by":"crossref","unstructured":"Gerke, S., Gim\u00e9nez, O., Noy, M., Wei\u00dfl, A., 2008. The number of graphs not containing K3,3 as a minor. Electronic J. of Combinatorics 15. doi: 10.37236\/838.","DOI":"10.37236\/838"},{"key":"10.1016\/j.procs.2025.10.281_bib16","doi-asserted-by":"crossref","unstructured":"Gim\u00e9nez, O., Noy, M., 2009. Counting planar graphs and related families of graphs, in: Surveys in Combinatorics, Cambridge University Press. pp. 169\u2013210. doi: 10.1017\/CBO9781107325975.008.","DOI":"10.1017\/CBO9781107325975.008"},{"key":"10.1016\/j.procs.2025.10.281_bib17","unstructured":"Gorsky, M., Seweryn, M.T., Wiederrecht, S., 2025. Polynomial Bounds for the Graph Minor Structure Theorem. Technical Report 2504.02532v1 [math.CO]. arXiv. doi: 10.48550\/arXiv.2504.02532. to appear in FOCS \u201825."},{"key":"10.1016\/j.procs.2025.10.281_bib18","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0012-365X(73)90067-8","article-title":"The number of caterpillars","volume":"6","author":"Harary","year":"1973","journal-title":"Disc. Math."},{"key":"10.1016\/j.procs.2025.10.281_bib19","doi-asserted-by":"crossref","unstructured":"Jia, L., Lin, G., Noubir, G., Rajaraman, R., Sundaram, R., 2005. Universal approximations for TSP, Steiner tree, and set cover, in: 37th Annual ACM Symp. on Theory of Computing (STOC), ACM Press. pp. 386\u2013395. doi: 10.1145\/1060590.1060649.","DOI":"10.1145\/1060590.1060649"},{"key":"10.1016\/j.procs.2025.10.281_bib20","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1137\/0405049","article-title":"Implicit representation of graphs","volume":"5","author":"Kannan","year":"1992","journal-title":"SIAM J. on Disc. Math."},{"key":"10.1016\/j.procs.2025.10.281_bib21","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1017\/S0963548307008619","article-title":"A short proof of the Hajnal-Szemer\u00e9di theorem on on equitable colouring","volume":"17","author":"Kierstead","year":"2008","journal-title":"Combinatorics, Probability and Computing"},{"key":"10.1016\/j.procs.2025.10.281_bib22","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1002\/jgt.20630","article-title":"Every 4-colorable graph with maximum degree 4 has an equitable 4-coloring","volume":"71","author":"Kierstead","year":"2012","journal-title":"J. of Graph Theory"},{"key":"10.1016\/j.procs.2025.10.281_bib23","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/s00493-010-2483-5","article-title":"A fast algorithm for equitable coloring","volume":"30","author":"Kierstead","year":"2010","journal-title":"Combinatorica"},{"key":"10.1016\/j.procs.2025.10.281_bib24","unstructured":"Kouekam, C., 2021. Induced universal graphs for edge-colored complete graphs. Master thesis. Karlsruhe Institute of Tech., Dept. of Informatics Institute of Theoretical Informatics. URL: http:\/\/i11www.iti.kit.edu\/_media\/teaching\/theses\/ma-kouekam-21.pdf."},{"key":"10.1016\/j.procs.2025.10.281_bib25","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01364272","article-title":"Homomorphieeigenschaften und mittlere Kantendichte von Graphen","volume":"174","author":"Mader","year":"1967","journal-title":"Math. Ann."},{"key":"10.1016\/j.procs.2025.10.281_bib26","doi-asserted-by":"crossref","first-page":"778","DOI":"10.1016\/j.jctb.2007.11.006","article-title":"Random graphs on surfaces","volume":"98","author":"McDiarmid","year":"2008","journal-title":"J. of Combinatorial Theory, Series B"},{"key":"10.1016\/j.procs.2025.10.281_bib27","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1002\/rsa.20447","article-title":"Random graphs containing few disjoint excluded minors","volume":"44","author":"McDiarmid","year":"2012","journal-title":"Random Structures and Algorithms"},{"key":"10.1016\/j.procs.2025.10.281_bib28","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1080\/00029890.1973.11993408","article-title":"Equitable coloring","volume":"80","author":"Meyer","year":"1973","journal-title":"The American Mathematical Monthly"},{"key":"10.1016\/j.procs.2025.10.281_bib29","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1002\/rsa.20893","article-title":"Further results on random cubic planar graphs","volume":"56","author":"Noy","year":"2020","journal-title":"Random Structures and Algorithms"},{"key":"10.1016\/j.procs.2025.10.281_bib30","doi-asserted-by":"crossref","first-page":"583","DOI":"10.2307\/1969046","article-title":"The number of trees","volume":"49","author":"Otter","year":"1948","journal-title":"Ann. of Math."},{"key":"10.1016\/j.procs.2025.10.281_bib31","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1006\/jctb.1994.1073","article-title":"Quickly excluding a planar graph","volume":"62","author":"Robertson","year":"1994","journal-title":"J. of Combinatorial Theory, Series B"},{"key":"10.1016\/j.procs.2025.10.281_bib32","doi-asserted-by":"crossref","first-page":"247","DOI":"10.7155\/jgaa.00529","article-title":"A note on universal point sets for planar graphs","volume":"24","author":"Scheucher","year":"2020","journal-title":"J. of Graph Algorithms and Applications"}],"container-title":["Procedia Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1877050925036282?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1877050925036282?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T08:20:52Z","timestamp":1764058852000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1877050925036282"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":32,"alternative-id":["S1877050925036282"],"URL":"https:\/\/doi.org\/10.1016\/j.procs.2025.10.281","relation":{},"ISSN":["1877-0509"],"issn-type":[{"value":"1877-0509","type":"print"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Lower Bounds for Induced-Universal Graphs","name":"articletitle","label":"Article Title"},{"value":"Procedia Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.procs.2025.10.281","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2025 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}