{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T20:44:55Z","timestamp":1725914695499},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319687049"},{"type":"electronic","value":"9783319687056"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-68705-6_28","type":"book-chapter","created":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T06:06:22Z","timestamp":1509516382000},"page":"372-385","source":"Crossref","is-referenced-by-count":2,"title":["On Low Rank-Width Colorings"],"prefix":"10.1007","author":[{"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"}]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,11,2]]},"reference":[{"key":"28_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/3-540-59071-4_56","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Deogun, J.S., Jansen, K., Kloks, T., Kratsch, D., M\u00fcller, H., Tuza, Z.: Rankings of graphs. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol. 903, pp. 292\u2013304. Springer, Heidelberg (1995). doi: 10.1007\/3-540-59071-4_56"},{"issue":"4","key":"28_CR2","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1007\/s00224-005-1199-1","volume":"39","author":"A Brandst\u00e4dt","year":"2006","unstructured":"Brandst\u00e4dt, A., Engelfriet, J., Le, H.O., Lozin, V.V.: Clique-width for 4-vertex forbidden subgraphs. Theory Comput. Syst. 39(4), 561\u2013590 (2006)","journal-title":"Theory Comput. Syst."},{"issue":"39","key":"28_CR3","doi-asserted-by":"crossref","first-page":"5187","DOI":"10.1016\/j.tcs.2011.05.022","volume":"412","author":"BM Bui-Xuan","year":"2011","unstructured":"Bui-Xuan, B.M., Telle, J.A., Vatshelle, M.: Boolean-width of graphs. Theoret. Comput. Sci. 412(39), 5187\u20135204 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"28_CR4","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1002\/jgt.21730","volume":"75","author":"M Chudnovsky","year":"2014","unstructured":"Chudnovsky, M.: The Erd\u00f6s-Hajnal conjecture\u2014a survey. J. Graph Theory 75(2), 178\u2013190 (2014)","journal-title":"J. Graph Theory"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: Handbook of Theoretical Computer Science, volume B, pp. 193\u2013242 (1990)","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"issue":"1","key":"28_CR6","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"issue":"2","key":"28_CR7","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46(2), 218\u2013270 (1993)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"28_CR8","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"5","key":"28_CR9","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1093\/comjnl\/bxv096","volume":"59","author":"K Dabrowski","year":"2016","unstructured":"Dabrowski, K., Paulusma, D.: Clique-width of graph classes defined by two forbidden induced subgraphs. Comput. J. 59(5), 650\u2013666 (2016)","journal-title":"Comput. J."},{"key":"28_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/3-540-57785-8_187","volume-title":"STACS 94","author":"JS Deogun","year":"1994","unstructured":"Deogun, J.S., Kloks, T., Kratsch, D., M\u00fcller, H.: On vertex ranking for permutation and other graphs. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol. 775, pp. 747\u2013758. Springer, Heidelberg (1994). doi: 10.1007\/3-540-57785-8_187"},{"issue":"1","key":"28_CR11","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.jctb.2003.09.001","volume":"91","author":"M DeVos","year":"2004","unstructured":"DeVos, M., Ding, G., Oporowski, B., Sanders, D.P., Reed, B., Seymour, P., Vertigan, D.: Excluding any graph as a minor allows a low tree-width 2-coloring. J. Comb. Theory, Series B 91(1), 25\u201341 (2004)","journal-title":"J. Comb. Theory, Series B"},{"key":"28_CR12","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012)","edition":"4"},{"issue":"5","key":"28_CR13","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1145\/2499483","volume":"60","author":"Z Dvo\u0159\u00e1k","year":"2013","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1l\u2019, D., Thomas, R.: Testing first-order properties for subclasses of sparse graphs. J. ACM (JACM) 60(5), 36 (2013)","journal-title":"J. ACM (JACM)"},{"issue":"4","key":"28_CR14","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1016\/j.ejc.2011.12.005","volume":"33","author":"Z Dvo\u0159\u00e1k","year":"2012","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1l\u2019, D.: Classes of graphs with small rank decompositions are $$\\chi $$ \u03c7 -bounded. Eur. J. Comb. 33(4), 679\u2013683 (2012)","journal-title":"Eur. J. Comb."},{"issue":"1\u20132","key":"28_CR15","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0166-218X(89)90045-0","volume":"25","author":"P Erd\u0151s","year":"1989","unstructured":"Erd\u0151s, P., Hajnal, A.: Ramsey-type theorems. Discret. Appl. Math. 25(1\u20132), 37\u201352 (1989)","journal-title":"Discret. Appl. Math."},{"key":"28_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/978-3-642-32589-2_38","volume-title":"Mathematical Foundations of Computer Science 2012","author":"R Ganian","year":"2012","unstructured":"Ganian, R., Hlin\u011bn\u1ef3, P., Ne\u0161et\u0159il, J., Obdr\u017e\u00e1lek, J., Ossona de Mendez, P., Ramadurai, R.: When trees grow low: shrubs and fast $${\\rm {MSO}}_1$$ MSO 1 . In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 419\u2013430. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-32589-2_38"},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kreutzer, S.: Methods for algorithmic meta theorems. In: Model Theoretic Methods in Finite Combinatorics, vol. 558, pp. 181\u2013206 (2011)","DOI":"10.1090\/conm\/558\/11051"},{"key":"28_CR18","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. In: STOC 2014, pp. 89\u201398. ACM (2014)","DOI":"10.1145\/2591796.2591851"},{"issue":"4","key":"28_CR19","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1016\/j.dam.2008.08.031","volume":"157","author":"F Gurski","year":"2009","unstructured":"Gurski, F., Wanke, E.: The NLC-width and clique-width for powers of graphs of bounded tree-width. Discret. Appl. Math. 157(4), 583\u2013595 (2009)","journal-title":"Discret. Appl. Math."},{"key":"28_CR20","first-page":"413","volume":"19","author":"A Gy\u00e1rf\u00e1s","year":"1987","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. Zastosowania Matematyki (Appl. Math.) 19, 413\u2013441 (1987)","journal-title":"Zastosowania Matematyki (Appl. Math.)"},{"issue":"3","key":"28_CR21","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1093\/comjnl\/bxm052","volume":"51","author":"P Hlin\u011bn\u1ef3","year":"2008","unstructured":"Hlin\u011bn\u1ef3, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51(3), 326\u2013362 (2008)","journal-title":"Comput. J."},{"issue":"3","key":"28_CR22","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1023\/B:ORDE.0000026489.93166.cb","volume":"20","author":"HA Kierstead","year":"2003","unstructured":"Kierstead, H.A., Yang, D.: Orderings on graphs and game coloring number. Order 20(3), 255\u2013264 (2003)","journal-title":"Order"},{"issue":"4","key":"28_CR23","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1007\/s00026-011-0117-2","volume":"15","author":"VV Lozin","year":"2011","unstructured":"Lozin, V.V.: Minimal classes of graphs of unbounded clique-width. Ann. Comb. 15(4), 707\u2013722 (2011)","journal-title":"Ann. Comb."},{"key":"28_CR24","first-page":"345","volume":"84","author":"VV Lozin","year":"2007","unstructured":"Lozin, V.V., Rudolf, G.: Minimal universal bipartite graphs. Ars Comb. 84, 345\u2013356 (2007)","journal-title":"Ars Comb."},{"issue":"6","key":"28_CR25","doi-asserted-by":"crossref","first-page":"1022","DOI":"10.1016\/j.ejc.2005.01.010","volume":"27","author":"J Ne\u0161et\u0159il","year":"2006","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb. 27(6), 1022\u20131041 (2006)","journal-title":"Eur. J. Comb."},{"issue":"3","key":"28_CR26","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1016\/j.ejc.2006.07.013","volume":"29","author":"J Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Grad and classes with bounded expansion I. Decompositions. Eur. J. Comb. 29(3), 760\u2013776 (2008)","journal-title":"Eur. J. Comb."},{"issue":"4","key":"28_CR27","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1016\/j.ejc.2011.01.006","volume":"32","author":"J Ne\u0161et\u0159il","year":"2011","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: On nowhere dense graphs. Eur. J. Comb. 32(4), 600\u2013617 (2011)","journal-title":"Eur. J. Comb."},{"issue":"6","key":"28_CR28","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1016\/S0195-6698(03)00064-7","volume":"24","author":"J Ne\u0161et\u0159il","year":"2003","unstructured":"Ne\u0161et\u0159il, J., Shelah, S.: On the order of countable graphs. Eur. J. Comb. 24(6), 649\u2013663 (2003)","journal-title":"Eur. J. Comb."},{"issue":"3","key":"28_CR29","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1002\/jgt.20280","volume":"57","author":"S Oum","year":"2008","unstructured":"Oum, S.: Rank-width is less than or equal to branch-width. J. Graph Theory 57(3), 239\u2013244 (2008)","journal-title":"J. Graph Theory"},{"key":"28_CR30","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.dam.2016.08.006","volume":"231","author":"S Oum","year":"2017","unstructured":"Oum, S.: Rank-width: agorithmic and structural results. Discret. Appl. Math. 231, 15\u201324 (2017)","journal-title":"Discret. Appl. Math."},{"key":"28_CR31","unstructured":"Oum, S., Seymour, P.: Personal communication"},{"issue":"4","key":"28_CR32","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S Oum","year":"2006","unstructured":"Oum, S., Seymour, P.: Approximating clique-width and branch-width. J. Comb. Theory, Series B 96(4), 514\u2013528 (2006)","journal-title":"J. Comb. Theory, Series B"},{"issue":"1","key":"28_CR33","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","volume":"89","author":"N Robertson","year":"2003","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XVI. Excluding a non-planar graph. J. Comb. Theory, Series B 89(1), 43\u201376 (2003)","journal-title":"J. Comb. Theory, Series B"},{"issue":"2","key":"28_CR34","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0020-0190(89)90161-0","volume":"33","author":"AA Sch\u00e4ffer","year":"1989","unstructured":"Sch\u00e4ffer, A.A.: Optimal node ranking of trees in linear time. Inf. Process. Lett. 33(2), 91\u201396 (1989)","journal-title":"Inf. Process. Lett."},{"key":"28_CR35","series-title":"Johns Hopkins Series in the Mathematical Sciences","doi-asserted-by":"crossref","DOI":"10.56021\/9780801844256","volume-title":"Combinatorics and Partially Ordered Sets","author":"WT Trotter","year":"1992","unstructured":"Trotter, W.T.: Combinatorics and Partially Ordered Sets. Johns Hopkins Series in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (1992)"},{"issue":"2\u20133","key":"28_CR36","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0166-218X(94)90026-4","volume":"54","author":"E Wanke","year":"1994","unstructured":"Wanke, E.: $$k$$ k -NLC graphs and polynomial algorithms. Discret. Appl. Math. 54(2\u20133), 251\u2013266 (1994)","journal-title":"Discret. Appl. Math."},{"issue":"18","key":"28_CR37","doi-asserted-by":"crossref","first-page":"5562","DOI":"10.1016\/j.disc.2008.03.024","volume":"309","author":"X Zhu","year":"2009","unstructured":"Zhu, X.: Colouring graphs with bounded generalized colouring number. Discret. Math. 309(18), 5562\u20135568 (2009)","journal-title":"Discret. Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-68705-6_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,27]],"date-time":"2023-08-27T20:50:23Z","timestamp":1693169423000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-68705-6_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319687049","9783319687056"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-68705-6_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}