{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:30Z","timestamp":1787321130857,"version":"build-2736575974"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE40-0028"],"award-info":[{"award-number":["ANR-16-CE40-0028"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-CE40-0025"],"award-info":[{"award-number":["ANR-18-CE40-0025"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010446","name":"Institute for Basic Science","doi-asserted-by":"publisher","award":["IBS-R029-C1"],"award-info":[{"award-number":["IBS-R029-C1"]}],"id":[{"id":"10.13039\/501100010446","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000275","name":"Leverhulme Trust","doi-asserted-by":"publisher","award":["RPG-2016-258"],"award-info":[{"award-number":["RPG-2016-258"]}],"id":[{"id":"10.13039\/501100000275","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2018R1D1A1B07050294"],"award-info":[{"award-number":["NRF-2018R1D1A1B07050294"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour [ J. Combin. Theory Ser. B, 35 (1983), pp. 39--61] proved that for every tree $T$, the class of graphs that do not contain $T$ as a minor has bounded path-width. For the pivot-minor relation, rank-width and linear rank-width take over the role of tree-width and path-width. As such, it is natural to examine if, for every tree $T$, the class of graphs that do not contain $T$ as a pivot-minor has bounded linear rank-width. We first prove that this statement is false whenever $T$ is a tree that is not a caterpillar. We conjecture that the statement is true if $T$ is a caterpillar. We are also able to give partial confirmation of this conjecture by proving for every tree $T$, the class of $T$-pivot-minor-free distance-hereditary graphs has bounded linear rank-width if and only if $T$ is a caterpillar; for every caterpillar $T$ on at most four vertices, the class of $T$-pivot-minor-free graphs has bounded linear rank-width. To prove our second result, we only need to consider $T=P_4$ and $T=K_{1,3}$, but we follow a general strategy: first we show that the class of $T$-pivot-minor-free graphs is contained in some class of $(H_1,H_2)$-free graphs, which we then show to have bounded linear rank-width. In particular, we prove that the class of $(K_3,S_{1,2,2})$-free graphs has bounded linear rank-width, which strengthens a known result that this graph class has bounded rank-width.<\/jats:p>","DOI":"10.1137\/21m1402339","type":"journal-article","created":{"date-parts":[[2021,12,7]],"date-time":"2021-12-07T11:11:15Z","timestamp":1638875475000},"page":"2922-2945","source":"Crossref","is-referenced-by-count":2,"title":["Tree Pivot-Minors and Linear Rank-Width"],"prefix":"10.1137","volume":"35","author":[{"given":"Konrad K.","family":"Dabrowski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fran\u00e7ois","family":"Dross","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jisu","family":"Jeong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mamadou M.","family":"Kant\u00e9","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1820-1962","authenticated-orcid":true,"given":"O-joung","family":"Kwon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6889-7286","authenticated-orcid":true,"given":"Sang-il","family":"Oum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,12,7]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.05.001"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.04.021"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0164-5"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2020.111926"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2020.01.038"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90068-U"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.03.012"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00747-x"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120210"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1989.tb22439.x"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1008"},{"key":"atypb12","unstructured":"A. Brandst\u00e4dt, S. Mahfud, and R. Mosca,\n                      Bounded Clique-Width of $({S}_{1,2,2}$, Triangle$)$-Free Graphs\n                      ,arXiv:1608.01820, 2016."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22730"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22037"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.09.012"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1980-057-7"},{"key":"atypb19","first-page":"125","author":"Dabrowski K. K.","year":"2018","journal-title":"Switzerland"},{"key":"atypb20","first-page":"577","volume":"88","author":"Dabrowski K. K.","year":"2019","journal-title":"S.)"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.06.005"},{"key":"atypb22","first-page":"1","volume":"456","author":"Dabrowski K. K.","year":"2019","journal-title":"London Math. Soc. Lecture Note Ser."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.06.030"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxv096"},{"key":"atypb25","first-page":"117","author":"Espelage W.","year":"2001","journal-title":"Berlin"},{"key":"atypb26","first-page":"38","author":"Ganian R.","year":"2011","journal-title":"Berlin"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"J. Geelen, O. Kwon, R. McCarty, and P. Wollan,\n                      The grid theorem for vertex-minors\n                      , J. Combin. Theory Ser. B, in press,https:\/\/doi.org\/10.1016\/j.jctb.2020.08.004.","DOI":"10.1016\/j.jctb.2020.08.004"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00725-9"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2740283"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2018.07.009"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/070691152"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00198-1"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2021.01.005"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.01.007"},{"key":"atypb35","first-page":"7","volume":"1","author":"Lozin V. V.","year":"2000","journal-title":"Diskretn. Anal. Issled. Oper. Ser."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00471-X"},{"key":"atypb37","unstructured":"V. V. Lozin and I. Razgon,\n                      Tree-Width Dichotomy\n                      ,arXiv:2012.01115, 2020."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054108005772"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2020.103223"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.03.003"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20353"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2016.08.006"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.10.006"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.03.043"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90079-5"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)90092-2"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1137\/0603036"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1402339","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:07:06Z","timestamp":1787317626000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1402339"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/21M1402339"],"URL":"https:\/\/doi.org\/10.1137\/21m1402339","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}