{"entities":{"Q895060":{"pageid":896908,"ns":120,"title":"Item:Q895060","lastrevid":65189724,"modified":"2026-04-12T00:54:29Z","type":"item","id":"Q895060","labels":{"en":{"language":"en","value":"A linear bound towards the traceability conjecture"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6513827"}},"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":"Q895060$A1BE4E8C-5E7A-48E1-B682-747613EA2AF4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ba38a44d293b5b29b30dbc237fc121d5a0ab34e3","datavalue":{"value":{"text":"A linear bound towards the traceability conjecture","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q895060$9C3FD613-798D-46B3-A558-F4978DCFF1F2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e5f5596749547fded7df5105667df7b324922b5e","datavalue":{"value":"1326.05058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q895060$38AE871C-F97E-4DFA-8086-C0702AF04220","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0dead522fa8201ca361d157d93130d4fe6858e72","datavalue":{"value":{"entity-type":"item","numeric-id":266955,"id":"Q266955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$CA223C67-1F5F-42F7-B568-43F1939A5448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4f2a546cf04984ddcbc10dc93ba3545e77a5a614","datavalue":{"value":{"entity-type":"item","numeric-id":266956,"id":"Q266956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$14150CF0-FAE1-4D9B-8B2A-50B888F50439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c260ff03eccd1c9575f407d3cab002fb4923248d","datavalue":{"value":{"entity-type":"item","numeric-id":244952,"id":"Q244952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$E676F84C-9448-4C7E-9DD7-B8FB7BE21167","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7e232b810ee203a7ce61c8327b62de28f5c27ad1","datavalue":{"value":{"entity-type":"item","numeric-id":1356463,"id":"Q1356463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$BA239E3A-37BF-41E5-8A1A-950569DCD1DF","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":"Q895060$3ED379E1-EF15-466F-9B4F-5E6448EB6712","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bd994e0b9bc80c86ef5ab9dd4c197e5cd2394cad","datavalue":{"value":{"time":"+2015-11-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q895060$0AC20A1F-88EE-4D62-B48D-00AE653B2F5B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"858d489a52abefa7bbc0548458199b2275b5d2e2","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p26","type":"string"},"datatype":"url"},"type":"statement","id":"Q895060$17C17994-4627-4E54-9820-953A3EBFB6B9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0013ac686350d40da629c6df0eda9478c3b2e8ca","datavalue":{"value":"Summary: A digraph is \\(k\\)-traceable if its order is at least \\(k\\) and each of its subdigraphs of order \\(k\\) is traceable. An oriented graph is a digraph without 2-cycles. The 2-traceable oriented graphs are exactly the nontrivial tournaments, so \\(k\\)-traceable oriented graphs may be regarded as generalized tournaments. It is well-known that all tournaments are traceable. We denote by \\(t(k)\\) the smallest integer bigger than or equal to \\(k\\) such that every \\(k\\)-traceable oriented graph of order at least \\(t(k)\\) is traceable. The traceability conjecture states that \\(t(k) \\leq 2k-1\\) for every \\(k\\geq 2\\) [the third author et al., ibid. 15, No. 1, Research Paper R150, 13 p. (2008; Zbl 1178.05046)]. We show that for \\(k \\geq 2\\), every \\(k\\)-traceable oriented graph with independence number 2 and order at least 4\\(k\\)-12 is traceable. This is the last open case in giving an upper bound for \\(t(k)\\) that is linear in \\(k\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q895060$1AF59D34-6DDB-4A35-914C-487F5597C010","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q895060$821711DD-F108-4805-89D3-DFACC409E6BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q895060$77F66AA3-2BF3-481B-9D84-679D2245C006","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8bc6aae83b4c4ee649515c1d15a2e012a12d9f2a","datavalue":{"value":"6513827","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q895060$D5810924-E637-4EEC-BA6C-0B4EEAFC6846","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d88254a5760b31b61e1fb0129d8fa4b56625290","datavalue":{"value":"oriented graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q895060$8CADB9AA-AD80-4DD1-A6F2-1BD68A3EDC10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"efbcb7b43bc033fcc9c5138d0c9919b0d7cef941","datavalue":{"value":"generalized tournament","type":"string"},"datatype":"string"},"type":"statement","id":"Q895060$6D3E988D-A99C-478F-AC0E-FDA9EEE45BB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef0984f79ec98eb27acd8c0453d1418a56010f15","datavalue":{"value":"\\(k\\)-traceable","type":"string"},"datatype":"string"},"type":"statement","id":"Q895060$4F9DC533-AA92-490C-A0E1-BE723AAE9F93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84d2404a6da479e58a9f5323bd4fe1b7971d1db9","datavalue":{"value":"traceability conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q895060$33D31C98-C3C5-4A8B-A8DA-CB46E04CD7A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a6abd881a56495780aafa106e4ce9af3a9f9fb7","datavalue":{"value":"path partition conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q895060$3A2BD5A4-B4F8-424D-A9AD-72255052709C","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":"Q895060$47921B6A-4BC5-482D-B913-77EBCCE4E32C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1d4c657f988b819627ab8864327408c13bf9ea2","datavalue":{"value":{"entity-type":"item","numeric-id":1953448,"id":"Q1953448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$64C79A97-051F-424E-A0A9-7D36F3D1A6BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0eb3382b3dc81d5167bcb8b8f23564551d92c342","datavalue":{"value":{"entity-type":"item","numeric-id":5492647,"id":"Q5492647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$02AE30DC-0282-456D-A719-5941E2E81C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1648ade3edd7e8911e0213d4d10fa1dcb749262d","datavalue":{"value":{"entity-type":"item","numeric-id":965994,"id":"Q965994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$D9C5F5A3-F612-477A-8009-A830C7E1AC2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"182dff32abd3746f92ff04072eb2e2ed57c19b4c","datavalue":{"value":{"entity-type":"item","numeric-id":641171,"id":"Q641171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$46E866B0-AA0F-4468-90A0-C9DD3C9FC5ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf27a3a17462a1e357558955de1a851b63219790","datavalue":{"value":{"entity-type":"item","numeric-id":1010888,"id":"Q1010888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$0542111D-B54B-4514-AE89-FDE4F089352D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b50a40a84a8da2c4c187fd01c7bb2ddbe3662a8","datavalue":{"value":{"entity-type":"item","numeric-id":742591,"id":"Q742591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$5F18829F-429E-4E29-B552-516140A2C78C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"867ac5df28d54c4379ce8e9a0ea9247d97b09a81","datavalue":{"value":{"entity-type":"item","numeric-id":2275358,"id":"Q2275358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$31ED8563-7A09-4E36-9A57-07B9C53E2D40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2481155a42676d821e036db9e722c8d7abd317aa","datavalue":{"value":{"entity-type":"item","numeric-id":5502988,"id":"Q5502988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$86B35A3D-C765-43C0-B5B2-C9098891D655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebade38ddfaf89228b6b45ac4d3ced1aae55aa16","datavalue":{"value":{"entity-type":"item","numeric-id":2501556,"id":"Q2501556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$1D56239A-5CC0-4236-A301-34804FC89A44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21c1152822730459e9de71876e40f61c6ce1320f","datavalue":{"value":{"entity-type":"item","numeric-id":396945,"id":"Q396945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$91364DC9-0724-4C6B-B730-E3081C98A87A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95cf0430c7b4d3b025fa7d1fb4f0308654be5bfd","datavalue":{"value":{"entity-type":"item","numeric-id":1837203,"id":"Q1837203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$DAC0BE59-52F9-4527-BE61-B38B30A25D15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e69e32f0d3231644ec9608af720173f67dd912b9","datavalue":{"value":{"entity-type":"item","numeric-id":3575434,"id":"Q3575434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$98C8F576-B91E-420D-B9DB-3D1BCED3F968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7df3d33b2e8b1f61e7d4c52554004f6e5e0552d","datavalue":{"value":{"entity-type":"item","numeric-id":1763350,"id":"Q1763350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$95C508AE-3706-46FD-B19C-A0183796AA9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1353d2952977fbf18a6627382605f90076a5b95b","datavalue":{"value":{"entity-type":"item","numeric-id":3309863,"id":"Q3309863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q895060$4C2D44F0-E2DF-4737-9949-6010573A0CA3","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"7e8b1c50f23646e806552f3ae2b03fb34376ac0f","datavalue":{"value":"bafkreib32rackp5auodmn36vgmgprkrd2iybahcps54co5fhllosavbe2y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q895060$25F8D743-418A-4260-BCF4-D6688A2D50BB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61234b3a33b4a76c79aad5de0fc03ee639301911","datavalue":{"value":{"entity-type":"item","numeric-id":3575434,"id":"Q3575434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0aaf7517b2f60de1f26e8e87a9b20639aebc3edc","datavalue":{"value":{"amount":"+0.9292640089988708","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":"Q895060$BD64395C-DE87-403B-8D1E-F814FD86B8AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"974f03f2deabf7447693ed6fc518f77638c52698","datavalue":{"value":{"entity-type":"item","numeric-id":965994,"id":"Q965994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fc96a03d220c20c9fe23155cdb9955fe9f3d890","datavalue":{"value":{"amount":"+0.918197751045227","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":"Q895060$1105846E-E7DA-4E73-9E41-E31EC5991ACD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d5fa037b6d75e39bcc552bb23b423e15eb794a4","datavalue":{"value":{"entity-type":"item","numeric-id":898141,"id":"Q898141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0bfa0da7c9734369fc35bb40873d83f1ccd28437","datavalue":{"value":{"amount":"+0.9111058712005616","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":"Q895060$69F0660F-505D-43B3-AD5F-F961C7EBAD74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e093e46c3d58837ba8bd8bd186ac6e41774a1ab4","datavalue":{"value":{"entity-type":"item","numeric-id":1010888,"id":"Q1010888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86d75b8e6e011f4bce427afd8deff4f0290ddd40","datavalue":{"value":{"amount":"+0.8964258432388306","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":"Q895060$32C1822A-95FB-4F87-8C74-1D6C86143A24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81c1b8418a5dabd3e4c83a4d0a458bd64cdff946","datavalue":{"value":{"entity-type":"item","numeric-id":396945,"id":"Q396945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd838a658969f9e5fff7e9f45084321de18535a6","datavalue":{"value":{"amount":"+0.8816476464271545","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":"Q895060$1C5E296C-26B0-486B-8F68-E6D9C25EF391","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A linear bound towards the traceability conjecture","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_linear_bound_towards_the_traceability_conjecture"}}}}}