{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:08Z","timestamp":1740109328848,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2024,3,29]],"date-time":"2024-03-29T00:00:00Z","timestamp":1711670400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,3,29]],"date-time":"2024-03-29T00:00:00Z","timestamp":1711670400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["GA21-32817S","GA21-32817S","GA21-32817S"],"award-info":[{"award-number":["GA21-32817S","GA21-32817S","GA21-32817S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,7]]},"DOI":"10.1007\/s00453-024-01220-9","type":"journal-article","created":{"date-parts":[[2024,3,29]],"date-time":"2024-03-29T10:01:43Z","timestamp":1711706503000},"page":"2174-2210","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Generalized Coloring of Permutations"],"prefix":"10.1007","volume":"86","author":[{"given":"V\u00edt","family":"Jel\u00ednek","sequence":"first","affiliation":[]},{"given":"Michal","family":"Opler","sequence":"additional","affiliation":[]},{"given":"Pavel","family":"Valtr","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,3,29]]},"reference":[{"key":"1220_CR1","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley Series in Computer Science and Information Processing, pp. 722\u20131. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont. (1973)"},{"issue":"5\u20136","key":"1220_CR2","first-page":"263","volume":"22","author":"A Brandst\u00e4dt","year":"1986","unstructured":"Brandst\u00e4dt, A., Kratsch, D.: On partitions of permutations into increasing and decreasing subsequences. Elektron Informationsverarb Kybernet 22(5\u20136), 263\u2013273 (1986)","journal-title":"Elektron Informationsverarb Kybernet"},{"issue":"1\u20133","key":"1220_CR3","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0012-365X(94)90242-9","volume":"132","author":"ZE Stankova","year":"1994","unstructured":"Stankova, Z.E.: Forbidden subsequences. Discrete Math. 132(1\u20133), 291\u2013316 (1994). https:\/\/doi.org\/10.1016\/0012-365X(94)90242-9","journal-title":"Discrete Math."},{"issue":"2","key":"1220_CR4","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/S0097-3165(96)80012-4","volume":"73","author":"AE K\u00e9zdy","year":"1996","unstructured":"K\u00e9zdy, A.E., Snevily, H.S., Wang, C.: Partitioning permutations into increasing and decreasing subsequences. J. Comb. Theory Ser. A 73(2), 353\u2013359 (1996). https:\/\/doi.org\/10.1016\/S0097-3165(96)80012-4","journal-title":"J. Comb. Theory Ser. A"},{"key":"1220_CR5","doi-asserted-by":"publisher","unstructured":"Atkinson, M.D.: Permutations which are the union of an increasing and a decreasing subsequence. Electron. J. Comb. 5, 6\u201313 (1998) https:\/\/doi.org\/10.37236\/1344","DOI":"10.37236\/1344"},{"key":"1220_CR6","unstructured":"Murphy, M.M.: Restricted Permutations, Antichains, Atomic Classes and Stack SD thesis, University of St Andrews (2003)"},{"issue":"2","key":"1220_CR7","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1002\/rsa.20140","volume":"31","author":"MH Albert","year":"2007","unstructured":"Albert, M.H.: On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation. Random Struct. Algorithms 31(2), 227\u2013238 (2007). https:\/\/doi.org\/10.1002\/rsa.20140","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"1220_CR8","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1216\/RMJ-2019-49-2-355","volume":"49","author":"M Albert","year":"2019","unstructured":"Albert, M., Pantone, J., Vatter, V.: On the growth of merges and staircases of permutation classes. Rocky Mt. J. Math. 49(2), 355\u2013367 (2019). https:\/\/doi.org\/10.1216\/RMJ-2019-49-2-355","journal-title":"Rocky Mt. J. Math."},{"issue":"8","key":"1220_CR9","doi-asserted-by":"publisher","first-page":"1680","DOI":"10.1016\/j.jcta.2012.05.006","volume":"119","author":"A Claesson","year":"2012","unstructured":"Claesson, A., Jel\u00ednek, V., Steingr\u00edmsson, E.: Upper bounds for the Stanley\u2013Wilf limit of 1324 and other layered patterns. J. Comb. Theory Ser. A 119(8), 1680\u20131691 (2012). https:\/\/doi.org\/10.1016\/j.jcta.2012.05.006","journal-title":"J. Comb. Theory Ser. A"},{"issue":"5","key":"1220_CR10","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1017\/S0963548314000091","volume":"23","author":"M B\u00f3na","year":"2014","unstructured":"B\u00f3na, M.: A new upper bound for 1324-avoiding permutations. Comb. Probab. Comput. 23(5), 717\u2013724 (2014). https:\/\/doi.org\/10.1017\/S0963548314000091","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"1220_CR11","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/s40879-014-0020-6","volume":"1","author":"M B\u00f3na","year":"2015","unstructured":"B\u00f3na, M.: A new record for 1324-avoiding permutations. Eur. J. Math. 1(1), 198\u2013206 (2015). https:\/\/doi.org\/10.1007\/s40879-014-0020-6","journal-title":"Eur. J. Math."},{"key":"1220_CR12","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.ejc.2020.103115","volume":"88","author":"D Bevan","year":"2020","unstructured":"Bevan, D., Brignall, R., Elvey Price, A., Pantone, J.: A structural characterisation of $${\\rm Av}(1324)$$ and new bounds on its growth rate. Eur. J. Combin. 88, 103\u2013115 (2020). https:\/\/doi.org\/10.1016\/j.ejc.2020.103115","journal-title":"Eur. J. Combin."},{"key":"1220_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.aam.2014.10.003","volume":"63","author":"V Jel\u00ednek","year":"2015","unstructured":"Jel\u00ednek, V., Valtr, P.: Splittings and Ramsey properties of permutation classes. Adv. Appl. Math. 63, 41\u201367 (2015). https:\/\/doi.org\/10.1016\/j.aam.2014.10.003","journal-title":"Adv. Appl. Math."},{"issue":"2","key":"1220_CR14","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1109\/mcse.2017.25","volume":"19","author":"V Jel\u00ednek","year":"2017","unstructured":"Jel\u00ednek, V., Opler, M.: Splittability and 1-amalgamability of permutation classes. Discrete Math. Theor. Comput. Sci. 19(2), 4\u201314 (2017). https:\/\/doi.org\/10.1109\/mcse.2017.25","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"1220_CR15","doi-asserted-by":"publisher","unstructured":"Albert, M., Jel\u00ednek, V.: Unsplittable classes of separable permutations. Electron. J. Comb. 23(2), 2\u20134920 (2016) https:\/\/doi.org\/10.37236\/6115","DOI":"10.37236\/6115"},{"key":"1220_CR16","doi-asserted-by":"publisher","unstructured":"Vatter, V.: An Erd\u0151s\u2013Hajnal analogue for permutation classes. Discrete Math. Theor. Comput. Sci. 18(2), 4\u20135 (2016) https:\/\/doi.org\/10.46298\/dmtcs.1328","DOI":"10.46298\/dmtcs.1328"},{"issue":"5","key":"1220_CR17","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0020-0190(97)00209-3","volume":"65","author":"P Bose","year":"1998","unstructured":"Bose, P., Buss, J.F., Lubiw, A.: Pattern matching for permutations. Inf. Process. Lett. 65(5), 277\u2013283 (1998). https:\/\/doi.org\/10.1016\/S0020-0190(97)00209-3","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1220_CR18","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1137\/S0895480104444776","volume":"22","author":"S Ahal","year":"2008","unstructured":"Ahal, S., Rabinovich, Y.: On complexity of the subpattern problem. SIAM J. Discrete Math. 22(2), 629\u2013649 (2008). https:\/\/doi.org\/10.1137\/S0895480104444776","journal-title":"SIAM J. Discrete Math."},{"key":"1220_CR19","doi-asserted-by":"publisher","unstructured":"Guillemot, S., Marx, D.: Finding small patterns in permutations in linear time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 82\u2013101. ACM, New York (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.7","DOI":"10.1137\/1.9781611973402.7"},{"key":"1220_CR20","doi-asserted-by":"publisher","unstructured":"Rutenburg, V.: Complexity of generalized graph coloring. In: Mathematical Foundations of Computer Science, 1986 (Bratislava, 1986). Lecture Notes in Computer Science, vol. 233, pp. 573\u2013581. Springer, Berlin (1986). https:\/\/doi.org\/10.1007\/BFb0016284","DOI":"10.1007\/BFb0016284"},{"key":"1220_CR21","doi-asserted-by":"publisher","unstructured":"Farrugia, A.: Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. Electron. J. Combin. 11(1), 46\u20139 (2004) https:\/\/doi.org\/10.37236\/1799","DOI":"10.37236\/1799"},{"issue":"3","key":"1220_CR22","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0166-218X(96)00096-0","volume":"69","author":"JI Brown","year":"1996","unstructured":"Brown, J.I.: The complexity of generalized graph colorings. Discrete Appl. Math. 69(3), 257\u2013270 (1996). https:\/\/doi.org\/10.1016\/0166-218X(96)00096-0","journal-title":"Discrete Appl. Math."},{"key":"1220_CR23","doi-asserted-by":"publisher","unstructured":"Alekseev, V.E., Farrugia, A., Lozin, V.V.: New results on generalized graph coloring. Discrete Math. Theor. Comput. Sci. 6(2), 215\u2013221 (2004) https:\/\/doi.org\/10.46298\/dmtcs.311","DOI":"10.46298\/dmtcs.311"},{"issue":"1\u20133","key":"1220_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0012-365X(97)00022-8","volume":"179","author":"D Achlioptas","year":"1998","unstructured":"Achlioptas, D., Brown, J.I., Corneil, D.G., Molloy, M.S.O.: The existence of uniquely $$-G$$ colourable graphs. Discrete Math. 179(1\u20133), 1\u201311 (1998). https:\/\/doi.org\/10.1016\/S0012-365X(97)00022-8","journal-title":"Discrete Math."},{"issue":"2","key":"1220_CR25","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s10878-017-0185-2","volume":"35","author":"P Borowiecki","year":"2018","unstructured":"Borowiecki, P.: Computational aspects of greedy partitioning of graphs. J. Comb. Optim. 35(2), 641\u2013665 (2018). https:\/\/doi.org\/10.1007\/s10878-017-0185-2","journal-title":"J. Comb. Optim."},{"issue":"3","key":"1220_CR26","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1016\/j.ejc.2011.12.007","volume":"34","author":"T Ekim","year":"2013","unstructured":"Ekim, T., Heggernes, P., Meister, D.: Polar permutation graphs are polynomial-time recognisable. Eur. J. Comb. 34(3), 576\u2013592 (2013). https:\/\/doi.org\/10.1016\/j.ejc.2011.12.007","journal-title":"Eur. J. Comb."},{"key":"1220_CR27","unstructured":"Vatter, V.: Permutation classes. In: Handbook of Enumerative Combinatorics. Discrete Mathematics Applications (Boca Raton), pp. 753\u2013833. CRC Press, Boca Raton, FL (2015)"},{"issue":"4","key":"1220_CR28","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1112\/plms.12250","volume":"119","author":"V Vatter","year":"2019","unstructured":"Vatter, V.: Growth rates of permutation classes: from countable to uncountable. Proc. Lond. Math. Soc. 119(4), 960\u2013997 (2019). https:\/\/doi.org\/10.1112\/plms.12250","journal-title":"Proc. Lond. Math. Soc."},{"key":"1220_CR29","unstructured":"Berendsohn, B.A.: Complexity of Permutation Pattern Matching. Master\u2019s thesis, Freie Universit\u00e4t Berlin (2019)"},{"key":"1220_CR30","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"key":"1220_CR31","unstructured":"Comon, H., Dauchet, M., Gilleron, R., L\u00f6ding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications (2007). Available on: http:\/\/tata.gforge.inria.fr\/"},{"key":"1220_CR32","doi-asserted-by":"publisher","unstructured":"Jel\u00ednek, V., Opler, M., Pek\u00e1rek, J.: Long paths make pattern-counting hard, and deep trees make it harder. In: 16th International Symposium on Parameterized and Exact Computation. LIPIcs Leibniz International Proceedings of the Informatics, vol. 214, pp. 22\u201317. Schloss Dagstuhl Leibniz-Zent Informatics, Wadern (2021). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2021.22","DOI":"10.4230\/LIPIcs.IPEC.2021.22"},{"key":"1220_CR33","doi-asserted-by":"publisher","unstructured":"Jel\u00ednek, V., Kyn\u010dl, J.: Hardness of permutation pattern matching. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 378\u2013396. SIAM, Philadelphia, PA (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.24","DOI":"10.1137\/1.9781611974782.24"},{"key":"1220_CR34","doi-asserted-by":"publisher","unstructured":"Jel\u00ednek, V., Opler, M., Pek\u00e1rek, J.: A complexity dichotomy for permutation pattern matching on grid classes. In: 45th International Symposium on Mathematical Foundations of Computer Science. LIPIcs Leibniz International Proceedings of the Informatics, vol. 170, pp. 52\u201318. Schloss Dagstuhl Leibniz-Zent Informatics, Wadern (2020). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.52","DOI":"10.4230\/LIPIcs.MFCS.2020.52"},{"key":"1220_CR35","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.ejc.2019.01.001","volume":"78","author":"M Albert","year":"2019","unstructured":"Albert, M., Brignall, R., Ru\u0161kuc, N., Vatter, V.: Rationality for subclasses of 321-avoiding permutations. Eur. J. Comb. 78, 44\u201372 (2019). https:\/\/doi.org\/10.1016\/j.ejc.2019.01.001","journal-title":"Eur. J. Comb."},{"issue":"2","key":"1220_CR36","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A $$c^kn$$ 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016). https:\/\/doi.org\/10.1137\/130947374","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1220_CR37","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/0890-5401(90)90043-H","journal-title":"Inf. Comput."},{"key":"1220_CR38","first-page":"463","volume":"2","author":"P Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463\u2013470 (1935)","journal-title":"Compos. Math."},{"key":"1220_CR39","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, California, 1978), pp. 216\u2013226. ACM, New York (1978)","DOI":"10.1145\/800133.804350"},{"key":"1220_CR40","doi-asserted-by":"publisher","unstructured":"Ho\u00e0ng, C.T., Le, V.B.: $$P_4$$-free colorings and $$P_4$$-bipartite graphs. Discrete Math. Theor. Comput. Sci. 4(2), 109\u2013122 (2001) https:\/\/doi.org\/10.46298\/dmtcs.272","DOI":"10.46298\/dmtcs.272"},{"key":"1220_CR41","doi-asserted-by":"publisher","unstructured":"Jel\u00ednek, V., Opler, M., Valtr, P.: Generalized coloring of permutations. In: 26th European Symposium on Algorithms. LIPIcs. Leibniz International Proceedings of the Informatics, vol. 112, pp. 50\u201314. Schloss Dagstuhl Leibniz-Zent Informatics, Wadern (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.50","DOI":"10.4230\/LIPIcs.ESA.2018.50"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01220-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01220-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01220-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,12]],"date-time":"2024-08-12T12:10:16Z","timestamp":1723464616000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01220-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,29]]},"references-count":41,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["1220"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01220-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,3,29]]},"assertion":[{"value":"2 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}