{"entities":{"Q2138584":{"pageid":2149327,"ns":120,"title":"Item:Q2138584","lastrevid":71392650,"modified":"2026-04-13T21:57:55Z","type":"item","id":"Q2138584","labels":{"en":{"language":"en","value":"Trees contained in every orientation of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7525893"}},"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":"Q2138584$3EAEB6F6-C09D-4A60-9B4D-BF69CE9088E2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"24d3283b3f891158b28f10edc770c3264557abc3","datavalue":{"value":{"text":"Trees contained in every orientation of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2138584$CE6E13F6-3CD7-47EE-A22C-AB21C8D78B13","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"badab3e0cea4e1ba87f9ff7a0d8efec0b87c0fbf","datavalue":{"value":"1487.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138584$E9C14B0E-38F6-497E-A6FC-314C6C139D64","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"242f10e9718426da0bdf6ac84dbad94b5bce2fec","datavalue":{"value":"10.37236/10487","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138584$BDEEF00D-0002-4ABA-9475-3D811154F86E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"caf0bd54f257fe831f949242b57417e229c1c5e1","datavalue":{"value":{"entity-type":"item","numeric-id":2132399,"id":"Q2132399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$C25CBADF-6316-447A-9BDD-E04532042965","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":"Q2138584$1BAB098A-3E81-4C39-A0D1-27C6CB0A2123","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"08e3be17afd587c4497081d99b52e81a609dcb4b","datavalue":{"value":{"time":"+2022-05-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2138584$9371B619-6042-498B-93AD-32F938C41B5F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c9b72e00d0e6ccfa0a3ac1b9d51042cad653c115","datavalue":{"value":"Summary: For every graph \\(G\\), let \\(t(G)\\) denote the largest integer \\(t\\) such that every oriented tree of order \\(t\\) appears in every orientation of \\(G\\). \\textit{S. A. Burr} [in: Proceedings of the eleventh south-eastern conference on combinatorics, graph theory and computing, held at Florida Atlantic University, Boca Raton, Florida, from March 3--7, 1980. Vols. I, II. Winnipeg, MB: Utilitas Mathematica Publishing Inc. 227--239 (1980; Zbl 0453.05022)] conjectured that \\(t(G)\\geq 1+\\chi(G)/2\\) for all \\(G\\), and showed that \\(t(G)\\geq 1+ \\lfloor\\sqrt{\\chi(G)}\\rfloor\\); this bound remains the state of the art, apart from the multiplicative constant. We present an elementary argument that improves this bound whenever \\(G\\) has somewhat large chromatic number, showing that \\(t(G)\\geq \\lfloor \\chi(G)/\\log_2 v(G)\\rfloor\\) for all \\(G\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138584$105F37E1-57F8-4704-A21D-A4297E0B92E4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138584$2688731D-D3CD-4596-9C5F-C3E0DECB8206","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138584$E7F30B56-0720-468C-82E8-CA58E270C04F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138584$E3949B34-6B5C-442A-99E8-EC50FF2B99E4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"51a514f76c826d6ccaca87799101be12b9cdfad5","datavalue":{"value":"7525893","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138584$5C37E41F-69DD-41B5-90FB-CB54457D03B2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"492952222f0a3d8997097bc5e263a894a664b61a","datavalue":{"value":"oriented graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138584$7357B466-49BF-4823-B42F-0D429C3201E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4fe39de0877c2c85a5d2f2867fcf202b3d9e29c8","datavalue":{"value":"anti-dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138584$BC34C02D-6055-494E-9BCB-D402051537EC","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e3144e328017f6bc8effad2547f24843eb734519","datavalue":{"value":"Q113202459","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138584$AE3150B3-9CB1-45BE-B6FE-14A86E07A1BA","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":"Q2138584$4DB2AB36-EC7E-41DF-A1E0-98E1DE8015F7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"90ca6665f74b43c0e735c19596471739354d2ddb","datavalue":{"value":"https://doi.org/10.37236/10487","type":"string"},"datatype":"url"},"type":"statement","id":"Q2138584$FF889CE1-728F-4046-B256-E263B29350EB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e09bc25c725169f2ff6e13c0b659c4e2c614a8fa","datavalue":{"value":"W4229005845","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138584$E676CB56-06DF-4274-8D26-B5DE9D1C14A6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1826c468254f0070285ea5645dd6619c2a334598","datavalue":{"value":{"entity-type":"item","numeric-id":1946667,"id":"Q1946667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$CBBC8A60-A3FB-4039-8B8F-D491550CF84A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25231ef06a1f02fb62a69a3980bb8fdc32cbf6a2","datavalue":{"value":{"entity-type":"item","numeric-id":885298,"id":"Q885298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$FCC9D2B4-1C21-4360-966D-F45F809746F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6c6e30e71ec4191c814859d4ee8748fe67c73bf","datavalue":{"value":{"entity-type":"item","numeric-id":5903892,"id":"Q5903892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$BF5DB3E0-AF51-4176-A123-55DE5B7A07D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7baffa508f8c8d892f0a7cb4be57188445575036","datavalue":{"value":{"entity-type":"item","numeric-id":3900086,"id":"Q3900086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$4BC51EF6-4901-45D0-AC04-BF254C44D7BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea16e6e8f0bab28c7f932b28d71021a41326390c","datavalue":{"value":{"entity-type":"item","numeric-id":5918100,"id":"Q5918100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$7DF71ADE-AFF9-4D54-B18A-2D9ACD466FFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27b91fb34b309a1448e42736f924e3a5012ab649","datavalue":{"value":{"entity-type":"item","numeric-id":3253064,"id":"Q3253064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$7EA28F4A-87CB-4B97-B054-16E9DF6B9FF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bdd250a45275500c245c98aa669a4cad3fe76cd","datavalue":{"value":{"entity-type":"item","numeric-id":5545303,"id":"Q5545303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$8621AFB2-664C-4E0A-AF05-EF57FBC06208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c21b97a1c274a5f75c018b79e9170da70257e50a","datavalue":{"value":{"entity-type":"item","numeric-id":5617553,"id":"Q5617553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$272758E3-D47A-43C8-BF20-2AE37151A4F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5da3c34cbe83b7543278a5603734ea64b7688d19","datavalue":{"value":{"entity-type":"item","numeric-id":5957701,"id":"Q5957701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$332D2F0F-64BC-46A1-A0D5-3DDEDE83EFEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2e7e14e31d04ef82ae403dfabf9feaa8ed525b7","datavalue":{"value":{"entity-type":"item","numeric-id":2857428,"id":"Q2857428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$5A64CACF-FCA0-400C-AC2C-DEBB918E676E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2718a2d6eecd510354f8921e4c6039df2c832c6","datavalue":{"value":{"entity-type":"item","numeric-id":651033,"id":"Q651033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$73CFCFF1-123C-4C4C-8AF5-42473F28E3A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7d22b67d5e1dabae67ae0a8d43712b7303dcba1","datavalue":{"value":{"entity-type":"item","numeric-id":4684833,"id":"Q4684833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$B511BC4D-23E3-4315-B00F-6EE317E75A7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70b64c36f147f07e9132a04121c3023f0fae5bd8","datavalue":{"value":{"entity-type":"item","numeric-id":5539654,"id":"Q5539654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$EF568F14-4A94-4BFD-AFAA-70968FA14EDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec664d2066b5f2e12234c4576e6a77f5891581a4","datavalue":{"value":{"entity-type":"item","numeric-id":2232047,"id":"Q2232047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$F5E91E72-349A-4161-93DD-FDDCB605B885","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c9d5f997ad4e98faf4457159b52d629b48df3f6","datavalue":{"value":{"entity-type":"item","numeric-id":5331780,"id":"Q5331780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$4C4353CA-FAA9-4F2F-90DB-23706EC987FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da495eb504dd5388021b77645b1bf7f600361514","datavalue":{"value":{"entity-type":"item","numeric-id":3671196,"id":"Q3671196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$DBEF3F74-8871-4415-8D6C-44265C616BDA","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"bba1c24d08eedc204be592bd882ab704b214eb93","datavalue":{"value":"bafkreif7iwrl4asmcjeglc5hd4zsvlsvticqty425t2amw7l432tsrl5ve","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138584$F7670B5B-CCAC-4597-8102-7610DA91D9E0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2493bae2cac71b53b0d852172fca8e92b07c5701","datavalue":{"value":{"entity-type":"item","numeric-id":1946667,"id":"Q1946667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"013c87995a516e2b2639fdc457880e1563883ca0","datavalue":{"value":{"amount":"+0.8517786264419556","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":"Q2138584$A95B73AC-810E-43C1-BF73-88DF8F19AE61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e235053404f55e74b8cefbffca68ba9b703dd36","datavalue":{"value":{"entity-type":"item","numeric-id":4344206,"id":"Q4344206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b116912b300f248bfbba9cb95cc0777c7206a678","datavalue":{"value":{"amount":"+0.8011094927787781","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":"Q2138584$E53D5ADA-FA5E-4C8D-8764-7CC76FAF7C63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"604a6e6691638b5197b87a011ec0ede18d579480","datavalue":{"value":{"entity-type":"item","numeric-id":4646938,"id":"Q4646938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa47598a9b1c2190efa43d8e0c07e61e59ec5d8a","datavalue":{"value":{"amount":"+0.7971075773239136","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":"Q2138584$29FA8F3C-04B5-45FA-B0AA-4721520D4610","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10e75085c1cfb2c473384cf5af9e439deda2e87a","datavalue":{"value":{"entity-type":"item","numeric-id":4879159,"id":"Q4879159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eda074568c88bbfb528f6ab5576affc608d885f9","datavalue":{"value":{"amount":"+0.783564031124115","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":"Q2138584$94343B30-1505-4D40-BAE6-0B551E9EDB1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5483a46275e8a7266d941090d3a8a8dd7757b147","datavalue":{"value":{"entity-type":"item","numeric-id":1692708,"id":"Q1692708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eda074568c88bbfb528f6ab5576affc608d885f9","datavalue":{"value":{"amount":"+0.783564031124115","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":"Q2138584$06716F08-2903-4037-B03D-E10700A6695E","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138584$757E908B-A53A-47B2-9A75-3D985E12A7CE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Trees contained in every orientation of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Trees_contained_in_every_orientation_of_a_graph"}}}}}