{"entities":{"Q5970276":{"pageid":8147072,"ns":120,"title":"Item:Q5970276","lastrevid":53026925,"modified":"2026-01-24T01:55:37Z","type":"item","id":"Q5970276","labels":{"en":{"language":"en","value":"Burling graphs, chromatic number, and orthogonal tree-decompositions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6841879"}},"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":"Q5970276$E3C2E262-7F0B-4969-B4FB-20E4C0E084C4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e778c1acf7d43d788f8a014946ddc3d0fac1c1b1","datavalue":{"value":{"text":"Burling graphs, chromatic number, and orthogonal tree-decompositions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5970276$FE0370E0-B1FF-4A86-858D-C032A713AB01","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6fb2f41e24cec969f059af0cace220e67df6e34c","datavalue":{"value":"1380.05060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5970276$6EAC5666-F2D4-414C-98DD-D93FE4147DF8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eb43e4c4f1b169e3803b8b6726a3b03e15c78164","datavalue":{"value":{"entity-type":"item","numeric-id":170482,"id":"Q170482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$84CA64F9-8DDE-446E-B7B3-1AC851923D1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb1d48e699dcbd07426b1c3ee3831813e5c5d7b0","datavalue":{"value":{"entity-type":"item","numeric-id":412238,"id":"Q412238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$D5CCECD2-3A46-49F0-AC5F-7D9B0569A87E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4cd896cc324ed8d238532cc31bb366d571b9dcae","datavalue":{"value":{"entity-type":"item","numeric-id":377498,"id":"Q377498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$DC8702FE-D045-45E7-AA03-E4B99F4DF985","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a539e6b59a5781e06906f6b0f6a357a21edb017","datavalue":{"value":{"entity-type":"item","numeric-id":792346,"id":"Q792346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$988E95E3-E8E0-4E36-8D52-73D7DD3C1DC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2edb636548564610f885e26ad5e4aed54e810cf9","datavalue":{"value":{"entity-type":"item","numeric-id":521396,"id":"Q521396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$6841C9EB-19F6-4650-8241-872F9B0CA5DC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$8F145A53-CAF5-4548-AE91-D864390F6175","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4c98dc438f41659f2d190c3ff2966dca049d17da","datavalue":{"value":{"time":"+2018-02-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5970276$2F5B51DC-5012-4D6A-BC67-9824A29E30A5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"170d83f88c3c17db743f40af812c360945076074","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p35","type":"string"},"datatype":"url"},"type":"statement","id":"Q5970276$C8192BC4-DF84-463D-B4BB-C5AC06F7514E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f3b9fca60a2d94ebeebed5f4d88383a8f9de7433","datavalue":{"value":"Summary: A classic result of \\textit{E. Asplund} and \\textit{B. Gr\u00fcnbaum} [Math. Scand. 8, 181--188 (1960; Zbl 0095.17002)] states that intersection graphs of axis-aligned rectangles in the plane are \\(\\chi\\)-bounded. This theorem can be equivalently stated in terms of path-decompositions as follows: There exists a function \\(f:\\mathbb{N}\\rightarrow\\mathbb{N}\\) such that every graph that has two path-decompositions such that each bag of the first decomposition intersects each bag of the second in at most \\(k\\) vertices has chromatic number at most \\(f(k)\\). Recently, \\textit{V. Dujmovi\u0107} et al. [``Orthogonal tree decompositions of graph'', Preprint, \\url{arXiv:1701.05639}] asked whether this remains true more generally for two tree-decompositions. In this note we provide a negative answer: There are graphs with arbitrarily large chromatic number for which one can find two tree-decompositions such that each bag of the first decomposition intersects each bag of the second in at most two vertices. Furthermore, this remains true even if one of the two decompositions is restricted to be a path-decomposition. This is shown using a construction of triangle-free graphs with unbounded chromatic number due to \\textit{J. P. Burling} [On coloring problems of families of prototypes. University of Colorado, Boulder (PhD Thesis) (1965)], which we believe should be more widely known.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5970276$47ACCF95-7234-476C-BE0A-84358F9ADA39","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5970276$C8A446E1-6ABD-44AC-A8DB-70AF05AF5E69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5970276$55BC0F80-5CCB-46CC-9E8D-BD758C861FC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5970276$D303784E-DD01-4BA7-AA7A-06C7A4C9C621","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"496ef4602f804f7000bed184f9c131e29b0e1fb3","datavalue":{"value":"6841879","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5970276$C611DA1E-3885-498E-A47B-F47CF1150664","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56e7fca34c452381a57356a2418a828b70ad9fab","datavalue":{"value":"path decompositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q5970276$20B1E18D-535C-41E8-80F7-5B3C02A616A3","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":"Q5970276$4EC8CDC9-CE95-459E-9378-855B2A350625","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cee4bddc43ec049f0e7d0627723fd0c19ab3aa6","datavalue":{"value":{"entity-type":"item","numeric-id":3272975,"id":"Q3272975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$4320C75D-BEFC-4B78-93D2-6FA514DA0E7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"063a63bf7ae2ea54869823172f0fb85a17e4eee6","datavalue":{"value":{"entity-type":"item","numeric-id":252837,"id":"Q252837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$78D523BA-E0F7-4335-BA52-90CBC917F1FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d62e967816953cecad41268e715794a55d56323d","datavalue":{"value":{"entity-type":"item","numeric-id":3577833,"id":"Q3577833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$3788A8D8-5EDF-47B3-9904-61C6C6A7E321","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1677bd52e084386d8f146bb28a37d1bffab25d91","datavalue":{"value":{"entity-type":"item","numeric-id":4634649,"id":"Q4634649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$E1E81006-6D4D-472F-B73D-4242BBA0FA01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"623aa0450604b7dbc9a31360325845e4adb61259","datavalue":{"value":{"entity-type":"item","numeric-id":5530478,"id":"Q5530478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$6D4B26EB-3D8B-446E-9109-38B82D54C77C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e624126070d764c7d1c093d99e92a2357ea010b0","datavalue":{"value":{"entity-type":"item","numeric-id":1219893,"id":"Q1219893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$E5DF054C-A6AA-46DA-B342-8FA075A543FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00c3e95c570b9717dfda652e8089e8df5e5323f9","datavalue":{"value":{"entity-type":"item","numeric-id":3171423,"id":"Q3171423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$8328AD76-646D-45D9-9BC3-257CA591BE61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dc8e3a70353874ae71b2b5e055e522ed5b6378c","datavalue":{"value":{"entity-type":"item","numeric-id":5847741,"id":"Q5847741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$090ABBE0-61C2-4FA3-8FC2-12BFFE756A34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ff6f77d40482f83e6db5befe85dc9aa15ead31f","datavalue":{"value":{"entity-type":"item","numeric-id":401487,"id":"Q401487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$01217DA3-B8E9-4E7D-B5E4-9CD7D3F4DA0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3a1992fdcc5452ecb00e89a620b5c678474d2ba","datavalue":{"value":{"entity-type":"item","numeric-id":3129824,"id":"Q3129824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5970276$814EA6DA-A04E-437C-B40E-BC9D15C144A3","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"14def263e12d19573dfa45bd9dfad918f0720704","datavalue":{"value":"bafkreihlsj3hafgjejltbkbg6anfozrxk5atbfk3xmbupa33yuqu2nnnc4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5970276$776F66A1-F173-4CED-87DC-D72A095B7DDB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e1943e8fe105f0641a0e6b220a5a3aabdafad2a","datavalue":{"value":{"entity-type":"item","numeric-id":5915813,"id":"Q5915813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"510f911931e18412169dedd607c556605c95ce15","datavalue":{"value":{"amount":"+0.9995678067207336","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":"Q5970276$3A0A2294-497A-4594-9C6C-1E05B0E83FCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0045b04ec2d86c0701ef82ab72fa5d8edaf38dea","datavalue":{"value":{"entity-type":"item","numeric-id":2700996,"id":"Q2700996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"242f436114b33067aca5335a17eddf9976c4c562","datavalue":{"value":{"amount":"+0.8110572099685669","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":"Q5970276$854CB00E-A096-4200-9CA6-7020884A568A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f91867f8edcd0a6a99d160956162d3d5815a47f","datavalue":{"value":{"entity-type":"item","numeric-id":896001,"id":"Q896001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d4fa1229f6dbfabcf332f81e66e7975db60f7af","datavalue":{"value":{"amount":"+0.7472739815711975","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":"Q5970276$5923284F-BCEB-4282-BD2D-81DD14E201ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fde5a9b4ee644cee8e64f70f05c72c4070be1ef0","datavalue":{"value":{"entity-type":"item","numeric-id":5360884,"id":"Q5360884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bfc44c522bd00df03ecf35878b52ca7b3b345d0","datavalue":{"value":{"amount":"+0.7348611950874329","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":"Q5970276$43994102-2015-4744-886B-E4C61544014D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffab6fa8e836e0fe0737b01fc57aea2d83e90ee9","datavalue":{"value":{"entity-type":"item","numeric-id":401487,"id":"Q401487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58a74737180630d78304085f82aa25a7016b8376","datavalue":{"value":{"amount":"+0.7339016199111938","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":"Q5970276$6D4D644A-5F51-45A5-B134-6EA9B90DB4FF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5970276","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5970276"}}}}}