{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T18:24:18Z","timestamp":1765045458514,"version":"build-2065373602"},"reference-count":48,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T00:00:00Z","timestamp":1716336000000},"content-version":"vor","delay-in-days":1603,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100002701","name":"Ministry of Education","doi-asserted-by":"publisher","award":["NRF-2018R1D1A1B07050294"],"award-info":[{"award-number":["NRF-2018R1D1A1B07050294"]}],"id":[{"id":"10.13039\/501100002701","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010665","name":"H2020 Marie Sk\u0142odowska-Curie Actions","doi-asserted-by":"publisher","award":["665778"],"award-info":[{"award-number":["665778"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["UMO-2015\/19\/P\/ST6\/03998"],"award-info":[{"award-number":["UMO-2015\/19\/P\/ST6\/03998"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001870","name":"Fundacja na rzecz Nauki Polskiej","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001870","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":[[2020,1]]},"DOI":"10.1016\/j.ejc.2019.103002","type":"journal-article","created":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T06:41:09Z","timestamp":1565764869000},"page":"103002","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":4,"special_numbering":"C","title":["On low rank-width colorings"],"prefix":"10.1016","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1820-1962","authenticated-orcid":false,"given":"O-joung","family":"Kwon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6347-1198","authenticated-orcid":false,"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"1","key":"10.1016\/j.ejc.2019.103002_b1","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1137\/S0895480195282550","article-title":"Rankings of graphs","volume":"11","author":"Bodlaender","year":"1998","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"10.1016\/j.ejc.2019.103002_b2","doi-asserted-by":"crossref","first-page":"1159","DOI":"10.1137\/140981745","article-title":"The Erd\u0151s-Hajnal conjecture for long holes and antiholes","volume":"30","author":"Bonamy","year":"2016","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"10.1016\/j.ejc.2019.103002_b3","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/s00224-005-1199-1","article-title":"Clique-width for 4-vertex forbidden subgraphs","volume":"39","author":"Brandst\u00e4dt","year":"2006","journal-title":"Theory Comput. Syst."},{"issue":"39","key":"10.1016\/j.ejc.2019.103002_b4","doi-asserted-by":"crossref","first-page":"5187","DOI":"10.1016\/j.tcs.2011.05.022","article-title":"Boolean-width of graphs","volume":"412","author":"Bui-Xuan","year":"2011","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"10.1016\/j.ejc.2019.103002_b5","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1145\/506147.506148","article-title":"Map graphs","volume":"49","author":"Chen","year":"2002","journal-title":"J. ACM"},{"issue":"2","key":"10.1016\/j.ejc.2019.103002_b6","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1002\/jgt.21730","article-title":"The Erd\u0151s-Hajnal conjecture\u2014a survey","volume":"75","author":"Chudnovsky","year":"2014","journal-title":"J. Graph Theory"},{"issue":"12","key":"10.1016\/j.ejc.2019.103002_b7","doi-asserted-by":"crossref","first-page":"3498","DOI":"10.1016\/j.disc.2018.09.007","article-title":"Vertex-minors and the Erd\u0151s\u2013Hajnal conjecture","volume":"341","author":"Chudnovsky","year":"2018","journal-title":"Discrete Math."},{"key":"10.1016\/j.ejc.2019.103002_b8","series-title":"Handbook of Theoretical Computer Science, Volume B","first-page":"193","article-title":"Graph rewriting: An algebraic and logic approach","author":"Courcelle","year":"1990"},{"issue":"1","key":"10.1016\/j.ejc.2019.103002_b9","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","article-title":"The monadic second-order logic of graphs. I. Recognizable sets of finite graphs","volume":"85","author":"Courcelle","year":"1990","journal-title":"Inform. and Comput."},{"issue":"2","key":"10.1016\/j.ejc.2019.103002_b10","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","article-title":"Handle-rewriting hypergraph grammars","volume":"46","author":"Courcelle","year":"1993","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"10.1016\/j.ejc.2019.103002_b11","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s10878-009-9260-7","article-title":"Compact labelings for efficient first-order model-checking","volume":"21","author":"Courcelle","year":"2011","journal-title":"J. Comb. Optim."},{"issue":"2","key":"10.1016\/j.ejc.2019.103002_b12","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","article-title":"Linear time solvable optimization problems on graphs of bounded clique-width","volume":"33","author":"Courcelle","year":"2000","journal-title":"Theory Comput. Syst."},{"issue":"5","key":"10.1016\/j.ejc.2019.103002_b13","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1093\/comjnl\/bxv096","article-title":"Clique-width of graph classes defined by two forbidden induced subgraphs","volume":"59","author":"Dabrowski","year":"2016","journal-title":"Comput. J."},{"key":"10.1016\/j.ejc.2019.103002_b14","series-title":"STACS 1994","first-page":"747","article-title":"On vertex ranking for permutation and other graphs","author":"Deogun","year":"1994"},{"issue":"1","key":"10.1016\/j.ejc.2019.103002_b15","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.jctb.2003.09.001","article-title":"Excluding any graph as a minor allows a low tree-width 2-coloring","volume":"91","author":"DeVos","year":"2004","journal-title":"J. Combin. Theory Ser. B"},{"year":"2019","series-title":"Branch-depth: Generalizing tree-depth of graphs","author":"DeVos","key":"10.1016\/j.ejc.2019.103002_b16"},{"key":"10.1016\/j.ejc.2019.103002_b17","series-title":"Graph Theory","volume":"vol. 173","author":"Diestel","year":"2012"},{"issue":"5","key":"10.1016\/j.ejc.2019.103002_b18","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1145\/2499483","article-title":"Testing first-order properties for subclasses of sparse graphs","volume":"60","author":"Dvo\u0159\u00e1k","year":"2013","journal-title":"J. ACM"},{"issue":"4","key":"10.1016\/j.ejc.2019.103002_b19","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":"1\u20132","key":"10.1016\/j.ejc.2019.103002_b20","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0166-218X(89)90045-0","article-title":"Ramsey-type theorems","volume":"25","author":"Erd\u0151s","year":"1989","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.ejc.2019.103002_b21","series-title":"33rd International Symposium on Computational Geometry","article-title":"Erd\u0151s-Hajnal conjecture for graphs with bounded VC-dimension","volume":"vol. 77","author":"Fox","year":"2017"},{"key":"10.1016\/j.ejc.2019.103002_b22","series-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)","first-page":"126:1","article-title":"First-order interpretations of bounded expansion classes","volume":"vol. 107","author":"Gajarsk\u00fd","year":"2018"},{"key":"10.1016\/j.ejc.2019.103002_b23","series-title":"MFCS 2012","first-page":"419","article-title":"When trees grow low: shrubs and fast MSO1","volume":"vol. 7464","author":"Ganian","year":"2012"},{"key":"10.1016\/j.ejc.2019.103002_b24","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1090\/conm\/558\/11051","article-title":"Methods for algorithmic meta theorems","volume":"558","author":"Grohe","year":"2011","journal-title":"Model Theor. Methods Finite Combin."},{"key":"10.1016\/j.ejc.2019.103002_b25","series-title":"STOC 2014","first-page":"89","article-title":"Deciding first-order properties of nowhere dense graphs","author":"Grohe","year":"2014"},{"issue":"1","key":"10.1016\/j.ejc.2019.103002_b26","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s00224-003-1112-8","article-title":"Learnability and definability in trees and similar structures","volume":"37","author":"Grohe","year":"2004","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"10.1016\/j.ejc.2019.103002_b27","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1016\/j.dam.2008.08.031","article-title":"The NLC-width and clique-width for powers of graphs of bounded tree-width","volume":"157","author":"Gurski","year":"2009","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.ejc.2019.103002_b28","first-page":"413","article-title":"Problems from the world surrounding perfect graphs","volume":"19","author":"Gy\u00e1rf\u00e1s","year":"1987","journal-title":"Zastos. Mat. (Appl. Math.)"},{"issue":"3","key":"10.1016\/j.ejc.2019.103002_b29","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1093\/comjnl\/bxm052","article-title":"Width parameters beyond tree-width and their applications","volume":"51","author":"Hlin\u011bn\u1ef3","year":"2008","journal-title":"Comput. J."},{"issue":"3","key":"10.1016\/j.ejc.2019.103002_b30","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1023\/B:ORDE.0000026489.93166.cb","article-title":"Orderings on graphs and game coloring number","volume":"20","author":"Kierstead","year":"2003","journal-title":"Order"},{"key":"10.1016\/j.ejc.2019.103002_b31","series-title":"Graph-Theoretic Concepts in Computer Science","first-page":"372","article-title":"On low rank-width colorings","volume":"vol. 10520","author":"Kwon","year":"2017"},{"key":"10.1016\/j.ejc.2019.103002_b32","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.jctb.2018.09.002","article-title":"Caterpillars in Erd\u0151s\u2013Hajnal","volume":"136","author":"Liebenau","year":"2019","journal-title":"J. Combin. Theory Ser. B"},{"issue":"4","key":"10.1016\/j.ejc.2019.103002_b33","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1007\/s00026-011-0117-2","article-title":"Minimal classes of graphs of unbounded clique-width","volume":"15","author":"Lozin","year":"2011","journal-title":"Ann. Comb."},{"key":"10.1016\/j.ejc.2019.103002_b34","first-page":"345","article-title":"Minimal universal bipartite graphs","volume":"84","author":"Lozin","year":"2007","journal-title":"Ars Combin."},{"issue":"6","key":"10.1016\/j.ejc.2019.103002_b35","doi-asserted-by":"crossref","first-page":"1022","DOI":"10.1016\/j.ejc.2005.01.010","article-title":"Tree-depth, subgraph coloring and homomorphism bounds","volume":"27","author":"Ne\u0161et\u0159il","year":"2006","journal-title":"European J. Combin."},{"issue":"3","key":"10.1016\/j.ejc.2019.103002_b36","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1016\/j.ejc.2006.07.013","article-title":"Grad and classes with bounded expansion I. Decompositions","volume":"29","author":"Ne\u0161et\u0159il","year":"2008","journal-title":"European J. Combin."},{"issue":"4","key":"10.1016\/j.ejc.2019.103002_b37","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1016\/j.ejc.2011.01.006","article-title":"On nowhere dense graphs","volume":"32","author":"Ne\u0161et\u0159il","year":"2011","journal-title":"European J. Combin."},{"issue":"6","key":"10.1016\/j.ejc.2019.103002_b38","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1016\/S0195-6698(03)00064-7","article-title":"On the order of countable graphs","volume":"24","author":"Ne\u0161et\u0159il","year":"2003","journal-title":"European J. Combin."},{"issue":"3","key":"10.1016\/j.ejc.2019.103002_b39","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1002\/jgt.20280","article-title":"Rank-width is less than or equal to branch-width","volume":"57","author":"Oum","year":"2008","journal-title":"J. Graph Theory"},{"key":"10.1016\/j.ejc.2019.103002_b40","article-title":"Rank-width: Algorithmic and structural results","author":"Oum","year":"2016","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.ejc.2019.103002_b41","unstructured":"S. Oum, P. Seymour, Personal communication."},{"issue":"4","key":"10.1016\/j.ejc.2019.103002_b42","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"},{"issue":"1","key":"10.1016\/j.ejc.2019.103002_b43","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","article-title":"Graph minors. XVI. Excluding a non-planar graph","volume":"89","author":"Robertson","year":"2003","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"10.1016\/j.ejc.2019.103002_b44","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0020-0190(89)90161-0","article-title":"Optimal node ranking of trees in linear time","volume":"33","author":"Sch\u00e4ffer","year":"1989","journal-title":"Inform. Process. Lett."},{"year":"2018","series-title":"A survey of \u03c7-boundedness","author":"Scott","key":"10.1016\/j.ejc.2019.103002_b45"},{"key":"10.1016\/j.ejc.2019.103002_b46","series-title":"Combinatorics and Partially Ordered Sets","first-page":"xvi+307","author":"Trotter","year":"1992"},{"issue":"2\u20133","key":"10.1016\/j.ejc.2019.103002_b47","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0166-218X(94)90026-4","article-title":"k-NLC graphs and polynomial algorithms","volume":"54","author":"Wanke","year":"1994","journal-title":"Discrete Appl. Math."},{"issue":"18","key":"10.1016\/j.ejc.2019.103002_b48","doi-asserted-by":"crossref","first-page":"5562","DOI":"10.1016\/j.disc.2008.03.024","article-title":"Colouring graphs with bounded generalized colouring number","volume":"309","author":"Zhu","year":"2009","journal-title":"Discrete Math."}],"container-title":["European Journal of Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0195669819301039?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0195669819301039?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T04:08:13Z","timestamp":1759291693000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0195669819301039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":48,"alternative-id":["S0195669819301039"],"URL":"https:\/\/doi.org\/10.1016\/j.ejc.2019.103002","relation":{},"ISSN":["0195-6698"],"issn-type":[{"type":"print","value":"0195-6698"}],"subject":[],"published":{"date-parts":[[2020,1]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"On low rank-width colorings","name":"articletitle","label":"Article Title"},{"value":"European Journal of Combinatorics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ejc.2019.103002","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2019 Elsevier Ltd.","name":"copyright","label":"Copyright"}],"article-number":"103002"}}