{"entities":{"Q6038574":{"pageid":13120320,"ns":120,"title":"Item:Q6038574","lastrevid":58635495,"modified":"2026-04-06T02:52:53Z","type":"item","id":"Q6038574","labels":{"en":{"language":"en","value":"Twin-width can be exponential in treewidth"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7681170"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$0F5FFCA1-46E8-4605-85AD-C491E9813672","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"64e414a1ff373a8cf559804ab3311a814ae4893a","datavalue":{"value":{"text":"Twin-width can be exponential in treewidth","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6038574$9BFDFE01-023A-468B-94F7-0CD5975BC462","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"24b101754d9a5dc9af7af6e45a94a7561ff9b152","datavalue":{"value":"1514.05131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6038574$E9A398AE-6732-47D2-BE03-4CF09AE82748","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ffc9ab64882a7f9515eb87005caf9401aaf99b8","datavalue":{"value":{"entity-type":"item","numeric-id":307767,"id":"Q307767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$C43A4526-CC30-40CB-99EE-082382472788","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1971162c9c83745d74dc2a6a3b6febeeb190555","datavalue":{"value":{"entity-type":"item","numeric-id":2005722,"id":"Q2005722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$559A797D-C969-478C-A314-4EB2D32D791C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$74BEED48-21DC-4565-B82D-1D1C812B57B3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9ecd7bc4009759ac541a6ef3b502800194e178d2","datavalue":{"value":{"time":"+2023-05-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6038574$1880017C-762E-43D1-BB1C-2FA0EDE5AE83","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4d89c8b21cc35e34fa65e838e730d15854559f1c","datavalue":{"value":"https://arxiv.org/abs/2204.07670","type":"string"},"datatype":"url"},"type":"statement","id":"Q6038574$FEA698EA-E91C-4D4B-AB17-17CDF1B06805","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"137fbfa0db67b2a682cb99942cab52bf6dadfc40","datavalue":{"value":"A trigraph is a graph with some edges colored black, and some colored red. A (vertex) contraction consists of merging two non-necessarily adjacent) vertices, say, \\(u, v\\) into a vertex \\(w\\), and keeping every edge \\(wz\\) black if and only if \\(uz\\) and \\(vz\\) were previously black edges. The other edges incident to \\(w\\) become red (if not already), and the rest of the trigraph remains the same. A contraction sequence of an \\(n\\)-vertex graph \\(G\\) is a sequence of trigraphs \\(G = G_n, \\dots, G_1 = K_1\\) such that \\(G_i\\) is obtained from \\(G_{i+1}\\) by performing one contraction. A \\(d\\)-sequence is a contraction sequence in which every vertex of every trigraph has at most \\(d\\) red edges incident to it. The twin-width of \\(G\\), denoted by \\(tww(G)\\), is then the minimum integer \\(d\\) such that \\(G\\) admits a \\(d\\)-sequence. In this paper, the authors obtain the following result: For every real \\(0< \\varepsilon\\leq 1/2\\) and integer \\(t > 1/\\varepsilon\\), there is a graph \\(G_{t,\\varepsilon}\\) with a feedback vertex set of size \\(t\\) and such that \\(tww(G_{t,\\varepsilon}) > 2^{(1-\\varepsilon)t}\\).  In particular, their result shows that the twin-width is sometimes exponential in the treewidth, in the so-called oriented twin-width and grid number, and that adding an apex may multiply the twin-width by at least \\(2-\\varepsilon\\). Except for the one in oriented twin-width, these lower bounds are essentially tight.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6038574$BB562ED5-B316-4BF0-8A21-7B2D580E3477","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"708cabcc0b98d3046976c0749eab0ac75e1ea52e","datavalue":{"value":{"entity-type":"item","numeric-id":343758,"id":"Q343758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$20DD9E93-0E55-409B-8DF9-8C268F455CE3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6038574$35E31380-A49F-42C5-92F4-15D887A03FE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49261cbbd2f3b64e072aca4630c2592536037a47","datavalue":{"value":"05C83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6038574$DDDEA056-2EF9-47CA-A0F7-E7349A5D32BF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0e6094dfd150085338ddf25c0754be49991f2eb4","datavalue":{"value":"7681170","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6038574$9766EC18-E4D1-4500-9A9D-05DB7A38BFAA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q6038574$4C52163F-F42E-4C38-BC4E-893014AED29F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c52f7b4a553b1787b81b760bd70e732f8e5abf8","datavalue":{"value":"feedback vertex set","type":"string"},"datatype":"string"},"type":"statement","id":"Q6038574$06D09CB2-0562-4177-924B-1B3BB4828672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9e706f01f04d3e651ace372f04400475247691dd","datavalue":{"value":"mixed minor","type":"string"},"datatype":"string"},"type":"statement","id":"Q6038574$2647AE41-E51C-4A0F-B96E-BB2C1C640331","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$D31B729B-32FC-4A21-BB24-FC2A200B6AEF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"270610bdb98f351bd8bdf4eb26282c6fc32e063f","datavalue":{"value":{"entity-type":"item","numeric-id":5043639,"id":"Q5043639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$EA43BC51-7AC4-435A-88C1-D9611C7E7082","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef491e8ae4b2c77899bccd33fd3e7e5e5fb49944","datavalue":{"value":{"entity-type":"item","numeric-id":5062015,"id":"Q5062015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$E2029948-5E48-43B2-A2BB-8C9654C34D51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1da31d047675a09057570e3a90611f77ed28efa3","datavalue":{"value":{"entity-type":"item","numeric-id":6043180,"id":"Q6043180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$3DC10BA0-4253-4C86-AE0A-CAA63F419807","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0780a90784e649b8ec876e893b429ea8cc803d3e","datavalue":{"value":{"entity-type":"item","numeric-id":879159,"id":"Q879159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$7B6CA39F-BB93-435A-ABDE-429E5C616F1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fc9edae0a03709543906e3db1e6371feeaeac69","datavalue":{"value":{"entity-type":"item","numeric-id":5872927,"id":"Q5872927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$65C7406B-002C-4613-AE7E-F5F9C287A702","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"805fa55b044c9ba24711ffcc0842d00203a872f1","datavalue":{"value":{"entity-type":"item","numeric-id":5051371,"id":"Q5051371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$664F720C-C425-441A-B31F-23E38328629D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0fda03c91b837efb25cecee65ded09278c96af1","datavalue":{"value":{"entity-type":"item","numeric-id":2093574,"id":"Q2093574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$36D617D9-41E0-4446-BA41-4CF05CFEB9E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"641efc7ca106dc9ad048284a7c75753fa1e78947","datavalue":{"value":{"entity-type":"item","numeric-id":5066940,"id":"Q5066940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$4350A241-88C0-4CE3-B48D-AFB62A03B44D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09d8ae945d420c6d569e06def4cab47942175f88","datavalue":{"value":{"entity-type":"item","numeric-id":6039430,"id":"Q6039430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6038574$3A488D84-E0D3-4D5F-ADE7-F89B8F0E9DC4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"00d9f3546395abe2b987d6571971d4ca99f21c47","datavalue":{"value":"10.1016/J.JCTB.2023.01.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6038574$BF80897B-FD27-45AA-955C-7BFD14DD8643","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"913f7b33213de047e2172761b51a05761bfea0ce","datavalue":{"value":{"entity-type":"item","numeric-id":5043639,"id":"Q5043639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"442b9afb2635800a0d1acdf54987047e80b2cc7f","datavalue":{"value":{"amount":"+0.790695309638977","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6038574$1CBCCAE9-A850-4A3F-A7E5-C39684AF3635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f67e0e49539e36be7167b076efd5524a53305a25","datavalue":{"value":{"entity-type":"item","numeric-id":5051371,"id":"Q5051371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d505f3b830f5e397d3a5e57265536ee0e5cab1a","datavalue":{"value":{"amount":"+0.7849621772766113","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6038574$92CDD43A-B0A6-49BF-A48A-BD8AE1F14AB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f3963dcba0ae20d7b333d7b3d1097592210e5b4","datavalue":{"value":{"entity-type":"item","numeric-id":2065919,"id":"Q2065919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52e3af772f7a017266f35b81053bf7cd6e34cd1f","datavalue":{"value":{"amount":"+0.7548350095748901","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6038574$A6528F50-99BE-43D2-B675-1BA45BB5F17B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73f0915e439f75a0f6065973fa826d9a55c6f709","datavalue":{"value":{"entity-type":"item","numeric-id":5066940,"id":"Q5066940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4af89ed16b2d3fa2be5e48bbd53a12a6a81b77c","datavalue":{"value":{"amount":"+0.749397873878479","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6038574$B1C55A1E-2B5D-473E-B685-7F4CBAB6A2EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56df348edcfe2e71221db43b239514fb5be96cfd","datavalue":{"value":{"entity-type":"item","numeric-id":5317177,"id":"Q5317177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"343bf56929232a01b5e4a2a70285768a8df3d71c","datavalue":{"value":{"amount":"+0.7460667490959167","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6038574$3F9ADB74-DEFD-4086-882D-475DD90058AF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6038574","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6038574"}}}}}