{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T14:19:01Z","timestamp":1754144341341,"version":"3.41.2"},"reference-count":146,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T00:00:00Z","timestamp":1783641600000},"content-version":"am","delay-in-days":282,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"},{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2202961"],"award-info":[{"award-number":["DMS-2202961"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["European Journal of Combinatorics"],"published-print":{"date-parts":[[2025,10]]},"DOI":"10.1016\/j.ejc.2024.104092","type":"journal-article","created":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T03:13:23Z","timestamp":1733282003000},"page":"104092","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":1,"special_numbering":"C","title":["A survey of degree-boundedness"],"prefix":"10.1016","volume":"129","author":[{"given":"Xiying","family":"Du","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rose","family":"McCarty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"year":"2024","series-title":"Excluding a clique or a biclique in graphs of bounded induced matching treewidth","author":"Abrishami","key":"10.1016\/j.ejc.2024.104092_b1"},{"key":"10.1016\/j.ejc.2024.104092_b2","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1016\/j.ejc.2013.06.048","article-title":"Interpreting nowhere dense graph classes as a classical notion of model theory","volume":"36","author":"Adler","year":"2014","journal-title":"European J. Combin."},{"issue":"3","key":"10.1016\/j.ejc.2024.104092_b3","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/0097-3165(80)90030-8","article-title":"A note on Ramsey numbers","volume":"29","author":"Ajtai","year":"1980","journal-title":"J. Combin. Theory Ser. A"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b4","doi-asserted-by":"crossref","first-page":"1438","DOI":"10.1137\/23M1573082","article-title":"A Menger-type theorem for two induced paths","volume":"38","author":"Albrechtsen","year":"2024","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b5","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1007\/s00454-022-00376-x","article-title":"The \u025b-t-net problem","volume":"68","author":"Alon","year":"2022","journal-title":"Discrete Comput. Geom."},{"issue":"125","key":"10.1016\/j.ejc.2024.104092_b6","first-page":"256","article-title":"Convex polyhedra of finite volume in Loba\u010devski\u012d space","volume":"83","author":"Andreev","year":"1970","journal-title":"Mat. Sb. (N.S.)"},{"issue":"5","key":"10.1016\/j.ejc.2024.104092_b7","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1007\/s00493-017-3593-0","article-title":"Chromatic number of ordered graphs with forbidden ordered subgraphs","volume":"38","author":"Axenovich","year":"2018","journal-title":"Combinatorica"},{"key":"10.1016\/j.ejc.2024.104092_b8","doi-asserted-by":"crossref","DOI":"10.1017\/fms.2021.52","article-title":"Zarankiewicz\u2019s problem for semilinear hypergraphs","volume":"9","author":"Basit","year":"2021","journal-title":"Forum Math. Sigma"},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b9","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s11856-022-2446-8","article-title":"Expander spanning subgraphs with large girth","volume":"251","author":"Benjamini","year":"2022","journal-title":"Israel J. Math."},{"key":"10.1016\/j.ejc.2024.104092_b10","first-page":"114","article-title":"F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind","volume":"10","author":"Berge","year":"1961","journal-title":"Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b11","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1002\/rsa.20973","article-title":"Dynamic concentration of the triangle-free process","volume":"58","author":"Bohman","year":"2021","journal-title":"Random Structures Algorithms"},{"key":"10.1016\/j.ejc.2024.104092_b12","doi-asserted-by":"crossref","DOI":"10.4171\/jems\/1341","article-title":"Asymptotic dimension of minor-closed families and Assouad\u2013Nagata dimension of surfaces","author":"Bonamy","year":"2023","journal-title":"J. Eur. Math. Soc."},{"key":"10.1016\/j.ejc.2024.104092_b13","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/j.jctb.2021.10.005","article-title":"Degeneracy of Pt-free and C\u2a7et-free graphs with no large complete bipartite subgraphs","volume":"152","author":"Bonamy","year":"2022","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.ejc.2024.104092_b14","article-title":"Graphs of bounded cliquewidth are polynomially \u03c7-bounded","author":"Bonamy","year":"2020","journal-title":"Adv. Comb."},{"key":"10.1016\/j.ejc.2024.104092_b15","series-title":"17th International Symposium on Parameterized and Exact Computation","article-title":"Twin-width VIII: delineation and win-wins","volume":"vol. 249","author":"Bonnet","year":"2022"},{"key":"10.1016\/j.ejc.2024.104092_b16","series-title":"48th International Colloquium on Automata, Languages, and Programming","article-title":"Twin-width III: max independent set, min dominating set, and coloring","volume":"vol. 198","author":"Bonnet","year":"2021"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b17","article-title":"Twin-width II: small classes","volume":"2","author":"Bonnet","year":"2022","journal-title":"Comb. Theory"},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b18","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1006\/jctb.1994.1008","article-title":"Circle graph obstructions","volume":"60","author":"Bouchet","year":"1994","journal-title":"J. Combin. Theory Ser. B"},{"year":"2023","series-title":"On polynomial degree-boundedness","author":"Bourneuf","key":"10.1016\/j.ejc.2024.104092_b19"},{"year":"2023","series-title":"Bounded twin-width graphs are polynomially \u03c7-bounded","author":"Bourneuf","key":"10.1016\/j.ejc.2024.104092_b20"},{"key":"10.1016\/j.ejc.2024.104092_b21","article-title":"Separating polynomial \u03c7-boundedness from \u03c7-boundedness","author":"Bria\u0144ski","year":"2023","journal-title":"Combinatorica"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b22","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1137\/0406017","article-title":"Representations of planar graphs","volume":"6","author":"Brightwell","year":"1993","journal-title":"SIAM J. Discrete Math."},{"year":"2023","series-title":"Induced subgraph density. I. A loglog step towards Erd\u0151s-Hajnal","author":"Buci\u0107","key":"10.1016\/j.ejc.2024.104092_b23"},{"year":"1965","series-title":"On Coloring Problems of Families of Polytopes","author":"Burling","key":"10.1016\/j.ejc.2024.104092_b24"},{"key":"10.1016\/j.ejc.2024.104092_b25","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.jctb.2022.09.001","article-title":"A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number","volume":"158","author":"Carbonero","year":"2023","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b26","doi-asserted-by":"crossref","DOI":"10.37236\/4424","article-title":"Restricted frame graphs and a conjecture of scott","volume":"23","author":"Chalopin","year":"2016","journal-title":"Electron. J. Combin."},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b27","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1002\/jgt.21730","article-title":"The Erd\u0151s\u2013Hajnal conjecture\u2014A survey","volume":"75","author":"Chudnovsky","year":"2014","journal-title":"J. Graph Theory"},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b28","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","article-title":"The strong perfect graph theorem","volume":"164","author":"Chudnovsky","year":"2006","journal-title":"Ann. of Math. (2)"},{"issue":"6","key":"10.1016\/j.ejc.2024.104092_b29","doi-asserted-by":"crossref","first-page":"1057","DOI":"10.1007\/s00493-016-3467-x","article-title":"Induced subgraphs of graphs with large chromatic number. III. Long holes","volume":"37","author":"Chudnovsky","year":"2017","journal-title":"Combinatorica"},{"key":"10.1016\/j.ejc.2024.104092_b30","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.jctb.2021.05.001","article-title":"Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings","volume":"150","author":"Chudnovsky","year":"2021","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.ejc.2024.104092_b31","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1016\/j.jctb.2019.05.001","article-title":"Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes","volume":"140","author":"Chudnovsky","year":"2020","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b32","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1090\/noti1474","article-title":"A conceptual breakthrough in sphere packing","volume":"64","author":"Cohn","year":"2017","journal-title":"Notices Amer. Math. Soc."},{"key":"10.1016\/j.ejc.2024.104092_b33","series-title":"Combinatorial Optimization","first-page":"21","author":"Cornu\u00e9jols","year":"2001"},{"key":"10.1016\/j.ejc.2024.104092_b34","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1016\/j.jctb.2023.10.006","article-title":"Treewidth versus clique number. II. Tree-independence number","volume":"164","author":"Dallard","year":"2024","journal-title":"J. Combin. Theory Ser. B"},{"issue":"12","key":"10.1016\/j.ejc.2024.104092_b35","first-page":"5121","article-title":"Improved bounds for colouring circle graphs","volume":"150","author":"Davies","year":"2022","journal-title":"Proc. Amer. Math. Soc."},{"key":"10.1016\/j.ejc.2024.104092_b36","doi-asserted-by":"crossref","first-page":"1049","DOI":"10.1007\/s00493-021-4767-3","article-title":"Vertex-minor-closed classes are \u03c7-bounded","volume":"42","author":"Davies","year":"2022","journal-title":"Combinatorica"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b37","doi-asserted-by":"crossref","first-page":"1124","DOI":"10.1137\/21M1437573","article-title":"The \u03c7-Ramsey problem for triangle-free graphs","volume":"36","author":"Davies","year":"2022","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/j.ejc.2024.104092_b38","series-title":"37th International Symposium on Computational Geometry","article-title":"Colouring polygon visibility graphs and their generalizations","volume":"vol. 189","author":"Davies","year":"2021"},{"key":"10.1016\/j.ejc.2024.104092_b39","series-title":"37th International Symposium on Computational Geometry","article-title":"Colouring polygon visibility graphs and their generalizations","volume":"vol. 189","author":"Davies","year":"2021"},{"issue":"4","key":"10.1016\/j.ejc.2024.104092_b40","doi-asserted-by":"crossref","first-page":"1523","DOI":"10.1007\/s00454-023-00592-z","article-title":"Grounded L-graphs are polynomially \u03c7-bounded","volume":"70","author":"Davies","year":"2023","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"10.1016\/j.ejc.2024.104092_b41","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1112\/blms.12447","article-title":"Circle graphs are quadratically \u03c7-bounded","volume":"53","author":"Davies","year":"2021","journal-title":"Bull. Lond. Math. Soc."},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b42","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0012-365X(81)90255-7","article-title":"Local complementation and interlacement graphs","volume":"33","author":"de Fraysseix","year":"1981","journal-title":"Discrete Math."},{"issue":"4","key":"10.1016\/j.ejc.2024.104092_b43","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1002\/jgt.20534","article-title":"On a conjecture of Thomassen concerning subgraphs of large girth","volume":"67","author":"Dellamonica","year":"2011","journal-title":"J. Graph Theory"},{"issue":"6","key":"10.1016\/j.ejc.2024.104092_b44","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1016\/j.jctb.2011.04.002","article-title":"A note on Thomassen\u2019s conjecture","volume":"101","author":"Dellamonica","year":"2011","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.ejc.2024.104092_b45","doi-asserted-by":"crossref","first-page":"103186, 23","DOI":"10.1016\/j.ejc.2020.103186","article-title":"Branch-depth: generalizing tree-depth of graphs","volume":"90","author":"DeVos","year":"2020","journal-title":"European J. Combin."},{"year":"2023","series-title":"Induced C4-free subgraphs with large average degree","author":"Du","key":"10.1016\/j.ejc.2024.104092_b46"},{"key":"10.1016\/j.ejc.2024.104092_b47","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.ejc.2017.10.004","article-title":"Induced subdivisions and bounded expansion","volume":"69","author":"Dvo\u0159\u00e1k","year":"2018","journal-title":"European J. Combin."},{"issue":"4","key":"10.1016\/j.ejc.2024.104092_b48","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1016\/j.ejc.2011.12.005","article-title":"Classes of graphs with small rank decompositions are \u03c7-bounded","volume":"33","author":"Dvo\u0159\u00e1k","year":"2012","journal-title":"European J. Combin."},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b49","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1137\/20M1311156","article-title":"Sublinear separators in intersection graphs of convex shapes","volume":"35","author":"Dvo\u0159\u00e1k","year":"2021","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b50","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.1137\/15M1017569","article-title":"Strongly sublinear separators and polynomial expansion","volume":"30","author":"Dvo\u0159\u00e1k","year":"2016","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/j.ejc.2024.104092_b51","doi-asserted-by":"crossref","first-page":"34","DOI":"10.4153\/CJM-1959-003-9","article-title":"Graph theory and probability","volume":"11","author":"Erd\u0151s","year":"1959","journal-title":"Canad. J. Math."},{"key":"10.1016\/j.ejc.2024.104092_b52","first-page":"37","article-title":"Ramsey-type theorems","volume":"25","author":"Erd\u0151s","year":"1989"},{"key":"10.1016\/j.ejc.2024.104092_b53","series-title":"Combinatorial Theory and Its Applications, I-III (Proc. Colloq., Balatonf\u00fcred, 1969)","first-page":"377","article-title":"Some extremal problems in graph theory","volume":"vol. 4","author":"Erd\u0151s","year":"1970"},{"key":"10.1016\/j.ejc.2024.104092_b54","series-title":"Graph Colorings, Flows and Perfect Matchings","first-page":"24","author":"Esperet","year":"2017"},{"issue":"5","key":"10.1016\/j.ejc.2024.104092_b55","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1017\/S0963548319000026","article-title":"Separation choosability and dense bipartite induced subgraphs","volume":"28","author":"Esperet","year":"2019","journal-title":"Combin. Probab. Comput."},{"issue":"1274","key":"10.1016\/j.ejc.2024.104092_b56","first-page":"v+125","article-title":"The triangle-free process and the Ramsey number R(3,k)","volume":"263","author":"Fiz\u00a0Pontiveros","year":"2020","journal-title":"Mem. Amer. Math. Soc."},{"issue":"3","key":"10.1016\/j.ejc.2024.104092_b57","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1017\/S0963548309990459","article-title":"A separator theorem for string graphs and its applications","volume":"19","author":"Fox","year":"2010","journal-title":"Combin. Probab. Comput."},{"issue":"3","key":"10.1016\/j.ejc.2024.104092_b58","doi-asserted-by":"crossref","first-page":"1381","DOI":"10.1016\/j.aim.2012.03.011","article-title":"String graphs and incomparability graphs","volume":"230","author":"Fox","year":"2012","journal-title":"Adv. Math."},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b59","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1017\/S0963548313000412","article-title":"Applications of a new separator theorem for string graphs","volume":"23","author":"Fox","year":"2014","journal-title":"Combin. Probab. Comput."},{"issue":"6","key":"10.1016\/j.ejc.2024.104092_b60","doi-asserted-by":"crossref","first-page":"1785","DOI":"10.4171\/jems\/705","article-title":"A semi-algebraic version of Zarankiewicz\u2019s problem","volume":"19","author":"Fox","year":"2017","journal-title":"J. Eur. Math. Soc. (JEMS)"},{"key":"10.1016\/j.ejc.2024.104092_b61","series-title":"Graph Drawing and Network Visualization","first-page":"219","article-title":"Quasiplanar graphs, string graphs, and the Erd\u0151s-Gallai problem","volume":"vol. 13764","author":"Fox","year":"2023"},{"year":"2021","series-title":"On the Erd\u0151s-Purdy problem and the Zarankiewitz problem for semialgebraic graphs","author":"Frankl","key":"10.1016\/j.ejc.2024.104092_b62"},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b63","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0012-365X(83)90081-X","article-title":"On finite set-systems whose every intersection is a kernel of a star","volume":"47","author":"F\u00fcredi","year":"1983","journal-title":"Discrete Math."},{"issue":"4","key":"10.1016\/j.ejc.2024.104092_b64","doi-asserted-by":"crossref","DOI":"10.1145\/3383206","article-title":"A new perspective on FO model checking of dense graph classes","volume":"21","author":"Gajarsk\u00fd","year":"2020","journal-title":"ACM Trans. Comput. Log."},{"issue":"4","key":"10.1016\/j.ejc.2024.104092_b65","doi-asserted-by":"crossref","DOI":"10.1145\/3382093","article-title":"First-order interpretations of bounded expansion classes","volume":"21","author":"Gajarsk\u00fd","year":"2020","journal-title":"ACM Trans. Comput. Log."},{"key":"10.1016\/j.ejc.2024.104092_b66","series-title":"Proceedings of the 37th Annual ACM\/IEEE Symposium on Logic in Computer Science","article-title":"Stable graphs of bounded twin-width","author":"Gajarsk\u00fd","year":"2022"},{"key":"10.1016\/j.ejc.2024.104092_b67","series-title":"Mathematical Foundations of Computer Science 2012","first-page":"419","article-title":"When trees grow low: Shrubs and fast MSO1","author":"Ganian","year":"2012"},{"key":"10.1016\/j.ejc.2024.104092_b68","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.jctb.2020.08.004","article-title":"The grid theorem for vertex-minors","volume":"158","author":"Geelen","year":"2023","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b69","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/jgt.20363","article-title":"Circle graph obstructions under pivoting","volume":"61","author":"Geelen","year":"2009","journal-title":"J. Graph Theory"},{"year":"2023","series-title":"Graph minors and metric spaces","author":"Georgakopoulos","key":"10.1016\/j.ejc.2024.104092_b70"},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b71","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s00493-023-00061-4","article-title":"Induced subgraphs of induced subgraphs of large chromatic number","volume":"44","author":"Gir\u00e3o","year":"2024","journal-title":"Combinatorica"},{"year":"2024","series-title":"Induced subdivisions in Ks,s-free graphs with polynomial average degree","author":"Gir\u00e3o","key":"10.1016\/j.ejc.2024.104092_b72"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b73","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1002\/jgt.3190020209","article-title":"Perfect elimination and chordal bipartite graphs","volume":"2","author":"Golumbic","year":"1978","journal-title":"J. Graph Theory"},{"key":"10.1016\/j.ejc.2024.104092_b74","series-title":"Graph-Theoretic Concepts in Computer Science (Konstanz, 2000)","first-page":"196","article-title":"The tree-width of clique-width bounded graphs without Kn,n","volume":"vol. 1928","author":"Gurski","year":"2000"},{"key":"10.1016\/j.ejc.2024.104092_b75","series-title":"Infinite and Finite Sets (Colloq., Keszthely, 1973; Dedicated to P. Erd\u0151s on His 60th Birthday), Vols. I, II, III","first-page":"801","article-title":"On Ramsey covering-numbers","volume":"Vol. 10","author":"Gy\u00e1rf\u00e1s","year":"1975"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b76","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0012-365X(85)90044-5","article-title":"On the chromatic number of multiple interval graphs and overlap graphs","volume":"55","author":"Gy\u00e1rf\u00e1s","year":"1985","journal-title":"Discrete Math."},{"key":"10.1016\/j.ejc.2024.104092_b77","series-title":"Proceedings of the International Conference on Combinatorial Analysis and Its Applications (Pokrzywna, 1985)","first-page":"413","article-title":"Problems from the world surrounding perfect graphs","volume":"19","author":"Gy\u00e1rf\u00e1s","year":"1987"},{"issue":"3","key":"10.1016\/j.ejc.2024.104092_b78","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0012-365X(80)90230-7","article-title":"Induced subtrees in graphs of large chromatic number","volume":"30","author":"Gy\u00e1rf\u00e1s","year":"1980","journal-title":"Discrete Math."},{"issue":"6","key":"10.1016\/j.ejc.2024.104092_b79","doi-asserted-by":"crossref","first-page":"1712","DOI":"10.1137\/16M1079336","article-title":"Approximation algorithms for polynomial-expansion and low-density graphs","volume":"46","author":"Har-Peled","year":"2017","journal-title":"SIAM J. Comput."},{"year":"2024","series-title":"K\u0151v\u00e1ri-s\u00f3s-Tur\u00e1n theorem for hereditary families","author":"Hunter","key":"10.1016\/j.ejc.2024.104092_b80"},{"key":"10.1016\/j.ejc.2024.104092_b81","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.dam.2019.06.026","article-title":"Mim-width I. Induced path problems","volume":"278","author":"Jaffke","year":"2020","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.ejc.2024.104092_b82","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1007\/s00493-024-00095-2","article-title":"On the Zarankiewicz problem for graphs with bounded VC-dimension","volume":"44","author":"Janzer","year":"2024","journal-title":"Combinatorica"},{"key":"10.1016\/j.ejc.2024.104092_b83","doi-asserted-by":"crossref","DOI":"10.1017\/fmp.2023.19","article-title":"Resolution of the Erd\u0151s-Sauer problem on regular subgraphs","volume":"11","author":"Janzer","year":"2023","journal-title":"Forum Math. Pi"},{"key":"10.1016\/j.ejc.2024.104092_b84","series-title":"40th International Symposium on Computational Geometry (SoCG 2024)","first-page":"66:1","article-title":"Zarankiewicz\u2019s Problem via \u03f5-t-Nets","volume":"vol. 293","author":"Keller","year":"2024"},{"key":"10.1016\/j.ejc.2024.104092_b85","doi-asserted-by":"crossref","first-page":"50","DOI":"10.4064\/cm-3-1-50-57","article-title":"On a problem of k. Zarankiewicz","volume":"3","author":"K\u0151v\u00e1ri","year":"1954","journal-title":"Colloq. Math."},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b86","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1002\/jgt.3190180203","article-title":"Radius two trees specify \u03c7-bounded classes","volume":"18","author":"Kierstead","year":"1994","journal-title":"J. Graph Theory"},{"key":"10.1016\/j.ejc.2024.104092_b87","series-title":"Kontaktprobleme der konformen Abbildung","first-page":"141","author":"Koebe","year":"1936"},{"key":"10.1016\/j.ejc.2024.104092_b88","series-title":"Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"5249","article-title":"Induced-minor-free graphs: Separator theorem, subexponential algorithms, and improved hardness of recognition","author":"Korhonen","year":"2024"},{"issue":"1\u20133","key":"10.1016\/j.ejc.2024.104092_b89","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/S0012-365X(96)00344-5","article-title":"Covering and coloring polygon-circle graphs","volume":"163","author":"Kostochka","year":"1997","journal-title":"Discrete Math."},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b90","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0095-8956(91)90091-W","article-title":"String graphs. II. Recognizing string graphs is NP-hard","volume":"52","author":"Kratochv\u00edl","year":"1991","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b91","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s00493-004-0010-2","article-title":"Every graph of sufficiently large average degree contains a C4-free subgraph of large average degree","volume":"24","author":"K\u00fchn","year":"2004","journal-title":"Combinatorica"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b92","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/s00493-004-0017-8","article-title":"Induced subdivisions in Ks,s-free graphs of large average degree","volume":"24","author":"K\u00fchn","year":"2004","journal-title":"Combinatorica"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b93","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/s00493-019-4086-0","article-title":"Dense induced bipartite subgraphs in triangle-free graphs","volume":"40","author":"Kwan","year":"2020","journal-title":"Combinatorica"},{"key":"10.1016\/j.ejc.2024.104092_b94","series-title":"8th Innovations in Theoretical Computer Science Conference","article-title":"Separators in region intersection graphs","volume":"vol. 67","author":"Lee","year":"2017"},{"year":"2024","series-title":"Tree decompositions meet induced matchings: beyond max weight independent set","author":"Lima","key":"10.1016\/j.ejc.2024.104092_b95"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b96","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton","year":"1979","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/j.ejc.2024.104092_b97","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/j.jctb.2023.04.005","article-title":"Polynomial \u03c7-binding functions for t-broom-free graphs","volume":"162","author":"Liu","year":"2023","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b98","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1017\/S0963548317000542","article-title":"Induced Tur\u00e1n numbers","volume":"27","author":"Loh","year":"2018","journal-title":"Combin. Probab. Comput."},{"key":"10.1016\/j.ejc.2024.104092_b99","series-title":"Topics on Perfect Graphs","first-page":"29","article-title":"Normal hypergraphs and the weak perfect graph conjecture","volume":"vol. 88","author":"Lov\u00e1sz","year":"1984"},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b100","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1017\/S0963548313000400","article-title":"Near-optimal separators in string graphs","volume":"23","author":"Matou\u0161ek","year":"2014","journal-title":"Combin. Probab. Comput."},{"key":"10.1016\/j.ejc.2024.104092_b101","series-title":"Geometry, Structure and Randomness in Combinatorics","first-page":"61","article-title":"String graphs and separators","volume":"vol. 18","author":"Matou\u0161ek","year":"2015"},{"year":"2021","series-title":"Local Structure for Vertex-Minors","author":"McCarty","key":"10.1016\/j.ejc.2024.104092_b102"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b103","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1137\/20M1370744","article-title":"Dense induced subgraphs of dense bipartite graphs","volume":"35","author":"McCarty","year":"2021","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20133","key":"10.1016\/j.ejc.2024.104092_b104","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0012-365X(95)00316-O","article-title":"On bounding the chromatic number of L-graphs","volume":"154","author":"McGuinness","year":"1996","journal-title":"Discrete Math."},{"issue":"4","key":"10.1016\/j.ejc.2024.104092_b105","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/PL00007228","article-title":"Colouring arcwise connected sets in the plane. I","volume":"16","author":"McGuinness","year":"2000","journal-title":"Graphs Combin."},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b106","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/256292.256294","article-title":"Separators for sphere-packings and nearest neighbor graphs","volume":"44","author":"Miller","year":"1997","journal-title":"J. ACM"},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b107","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s11856-021-2236-8","article-title":"C4-free subgraphs with large average degree","volume":"246","author":"Montgomery","year":"2021","journal-title":"Israel J. Math."},{"key":"10.1016\/j.ejc.2024.104092_b108","doi-asserted-by":"crossref","DOI":"10.1016\/j.ejc.2020.103223","article-title":"Classes of graphs with low complexity: The case of classes with bounded linear rankwidth","volume":"91","author":"Ne\u0161et\u0159il","year":"2021","journal-title":"European J. Combin."},{"year":"2023","series-title":"Induced subgraph density. V. All paths approach Erd\u0151s-Hajnal","author":"Nguyen","key":"10.1016\/j.ejc.2024.104092_b109"},{"year":"2023","series-title":"Induced subgraph density. VII. The five-vertex path","author":"Nguyen","key":"10.1016\/j.ejc.2024.104092_b110"},{"year":"2024","series-title":"A counterexample to the coarse menger conjecture","author":"Nguyen","key":"10.1016\/j.ejc.2024.104092_b111"},{"year":"2024","series-title":"Induced subgraph density. VI. Bounded VC-dimension","author":"Nguyen","key":"10.1016\/j.ejc.2024.104092_b112"},{"year":"2024","series-title":"Subdivisions and near-linear stable sets","author":"Nguyen","key":"10.1016\/j.ejc.2024.104092_b113"},{"year":"2024","series-title":"Trees and near-linear stable sets","author":"Nguyen","key":"10.1016\/j.ejc.2024.104092_b114"},{"issue":"4","key":"10.1016\/j.ejc.2024.104092_b115","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","article-title":"Approximating clique-width and branch-width","volume":"96","author":"Oum","year":"2006","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.ejc.2024.104092_b116","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1016\/j.jctb.2013.11.001","article-title":"Triangle-free intersection graphs of line segments with large chromatic number","volume":"105","author":"Pawlik","year":"2014","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.ejc.2024.104092_b117","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/j.jctb.2023.02.006","article-title":"Graphs of bounded twin-width are quasi-polynomially \u03c7-bounded","volume":"161","author":"Pilipczuk","year":"2023","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b118","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1006\/jctb.1995.1004","article-title":"Dense graphs without 3-regular subgraphs","volume":"63","author":"Pyber","year":"1995","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b119","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","article-title":"Graph minors. XIII. The disjoint paths problem","volume":"63","author":"Robertson","year":"1995","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b120","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","article-title":"Graph minors. XX. Wagner\u2019s conjecture","volume":"92","author":"Robertson","year":"2004","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b121","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1090\/S0002-9939-1977-0469806-4","article-title":"On the chromatic number of subgraphs of a given graph","volume":"64","author":"R\u00f6dl","year":"1977","journal-title":"Proc. Amer. Math. Soc."},{"key":"10.1016\/j.ejc.2024.104092_b122","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","article-title":"On the density of families of sets","volume":"13","author":"Sauer","year":"1972","journal-title":"J. Combin. Theory Ser. A"},{"issue":"4","key":"10.1016\/j.ejc.2024.104092_b123","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1002\/(SICI)1097-0118(199704)24:4<297::AID-JGT2>3.0.CO;2-J","article-title":"Induced trees in graphs of large chromatic number","volume":"24","author":"Scott","year":"1997","journal-title":"J. Graph Theory"},{"key":"10.1016\/j.ejc.2024.104092_b124","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1016\/j.jctb.2020.01.004","article-title":"Induced subgraphs of graphs with large chromatic number. VI. Banana trees","volume":"145","author":"Scott","year":"2020","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"10.1016\/j.ejc.2024.104092_b125","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1002\/jgt.22601","article-title":"A survey of \u03c7-boundedness","volume":"95","author":"Scott","year":"2020","journal-title":"J. Graph Theory"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b126","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1002\/jgt.22862","article-title":"Polynomial bounds for chromatic number. III. Excluding a double star","volume":"101","author":"Scott","year":"2022","journal-title":"J. Graph Theory"},{"issue":"3","key":"10.1016\/j.ejc.2024.104092_b127","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1002\/jgt.22880","article-title":"Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree","volume":"102","author":"Scott","year":"2023","journal-title":"J. Graph Theory"},{"issue":"5","key":"10.1016\/j.ejc.2024.104092_b128","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1007\/s00493-023-00015-w","article-title":"Polynomial bounds for chromatic number. IV: A near-polynomial bound for excluding the five-vertex path","volume":"43","author":"Scott","year":"2023","journal-title":"Combinatorica"},{"issue":"1","key":"10.1016\/j.ejc.2024.104092_b129","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1006\/jctb.1993.1027","article-title":"Graph searching and a min-max theorem for tree-width","volume":"58","author":"Seymour","year":"1993","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.ejc.2024.104092_b130","doi-asserted-by":"crossref","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","article-title":"A combinatorial problem; stability and order for models and theories in infinitary languages","volume":"41","author":"Shelah","year":"1972","journal-title":"Pacific J. Math."},{"key":"10.1016\/j.ejc.2024.104092_b131","series-title":"Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280)","first-page":"232","article-title":"Geometric separator theorems and applications","author":"Smith","year":"1998"},{"year":"2024","series-title":"A survey of zarankiewicz problem in geometry","author":"Smorodinsky","key":"10.1016\/j.ejc.2024.104092_b132"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b133","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/s00454-012-9420-x","article-title":"An incidence theorem in higher dimensions","volume":"48","author":"Solymosi","year":"2012","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"10.1016\/j.ejc.2024.104092_b134","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1112\/blms.12457","article-title":"Hasse diagrams with large chromatic number","volume":"53","author":"Suk","year":"2021","journal-title":"Bull. Lond. Math. Soc."},{"key":"10.1016\/j.ejc.2024.104092_b135","series-title":"The Theory and Applications of Graphs (Kalamazoo, Mich., 1980)","first-page":"557","article-title":"Subtrees of a graph and the chromatic number","author":"Sumner","year":"1981"},{"issue":"3\u20134","key":"10.1016\/j.ejc.2024.104092_b136","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF02579194","article-title":"Extremal problems in discrete geometry","volume":"3","author":"Szemer\u00e9di","year":"1983","journal-title":"Combinatorica"},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b137","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0095-8956(83)90067-9","article-title":"Girth in graphs","volume":"35","author":"Thomassen","year":"1983","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.ejc.2024.104092_b138","series-title":"The Geometry and Topology of Three-Manifolds. Vol. IV","first-page":"xvii+316","author":"Thurston","year":"2022"},{"issue":"6","key":"10.1016\/j.ejc.2024.104092_b139","doi-asserted-by":"crossref","first-page":"982","DOI":"10.1017\/S0963548321000171","article-title":"Tur\u00e1n-type results for intersection graphs of boxes","volume":"30","author":"Tomon","year":"2021","journal-title":"Combin. Probab. Comput."},{"key":"10.1016\/j.ejc.2024.104092_b140","series-title":"2023 IEEE 64th Annual Symposium on Foundations of Computer Science","first-page":"663","article-title":"Flip-width: Cops and robber on dense graphs","author":"Toru\u0144czyk","year":"2023"},{"year":"2012","series-title":"New Width Parameters of Graphs","author":"Vatshelle","key":"10.1016\/j.ejc.2024.104092_b141"},{"issue":"5","key":"10.1016\/j.ejc.2024.104092_b142","first-page":"9","article-title":"Critical graphs with given chromatic class","author":"Vizing","year":"1965","journal-title":"Diskret. Analiz"},{"key":"10.1016\/j.ejc.2024.104092_b143","doi-asserted-by":"crossref","DOI":"10.1016\/j.ejc.2023.103831","article-title":"Coloring triangle-free L-graphs with O(loglogn) colors","volume":"117","author":"Walczak","year":"2024","journal-title":"European J. Combin."},{"issue":"2","key":"10.1016\/j.ejc.2024.104092_b144","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1007\/s00222-020-00975-6","article-title":"The polynomial method over varieties","volume":"222","author":"Walsh","year":"2020","journal-title":"Invent. Math."},{"key":"10.1016\/j.ejc.2024.104092_b145","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/j.jctb.2019.04.004","article-title":"In absence of long chordless cycles, large tree-width becomes a local phenomenon","volume":"139","author":"Wei\u00dfauer","year":"2019","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.ejc.2024.104092_b146","series-title":"Proceedings of the Twenty-NInth Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"219","article-title":"Minor-matching hypertree width","author":"Yolov","year":"2018"}],"container-title":["European Journal of Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S019566982400177X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S019566982400177X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,7,15]],"date-time":"2025-07-15T12:31:26Z","timestamp":1752582686000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S019566982400177X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10]]},"references-count":146,"alternative-id":["S019566982400177X"],"URL":"https:\/\/doi.org\/10.1016\/j.ejc.2024.104092","relation":{},"ISSN":["0195-6698"],"issn-type":[{"type":"print","value":"0195-6698"}],"subject":[],"published":{"date-parts":[[2025,10]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"A survey of degree-boundedness","name":"articletitle","label":"Article Title"},{"value":"European Journal of Combinatorics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ejc.2024.104092","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2025 Elsevier Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"104092"}}