{"entities":{"Q1301658":{"pageid":1312408,"ns":120,"title":"Item:Q1301658","lastrevid":68407239,"modified":"2026-04-12T23:30:12Z","type":"item","id":"Q1301658","labels":{"en":{"language":"en","value":"Forbidden triples and traceability: A characterization"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1334480"}},"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":"Q1301658$4A3B1A59-7C84-48B7-9CC1-38C106A0BBD3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2968e3c3e90c8f58fca6353e9fa663689de0562c","datavalue":{"value":{"text":"Forbidden triples and traceability: A characterization","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1301658$CB588F89-2E37-4DA3-A488-41B2B6671241","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1a0fcceb2114295d621f9277ef6838577bca375e","datavalue":{"value":"0935.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301658$B4CA8694-9F54-4B14-BC61-3ADE8A3D5532","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bd28e1e07653da58f7746f150441aea765fbb97b","datavalue":{"value":"10.1016/S0012-365X(99)00021-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301658$04BFC9F5-809D-4292-B329-81A7671EB7AE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"46a94d04410c6537d8cdaa956c63781ba0b67be4","datavalue":{"value":{"entity-type":"item","numeric-id":175503,"id":"Q175503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301658$54EF7E76-A8ED-4FC1-8D3C-7D98D4062625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"030e5cf93b1f0c65c6aee9cb1331e1b67f361d03","datavalue":{"value":{"entity-type":"item","numeric-id":848766,"id":"Q848766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301658$394516E6-2071-431B-A8CC-A62687FF9F91","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301658$1AEB1863-EDA2-407A-B3FA-1B2C7FEFDE83","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bc2df620fd6a8df372731edb4d2b9ffdc4ef3885","datavalue":{"value":{"time":"+2000-05-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1301658$63E24EC0-907B-4CFC-9FD7-CC376FA06072","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6877d30b6b6fcf45b6575020aa8a683d0f6998ae","datavalue":{"value":"All graphs investigated in the paper are simple ones. If \\(G\\) is a connected graph and \\({\\mathfrak F}\\) is a family of connected graphs then \\({\\mathfrak F}\\) is called a forbidden family if no induced subgraph of \\(G\\) is isomorphic to any graph in \\({\\mathfrak F}\\) and \\(G\\) is said to be \\({\\mathfrak F}\\)-free. A graph is said to be traceable if it contains a path that spans the vertex set.   In two previous papers the authors have found four distinct families of triples of subgraphs which imply traceability when they are forbidden in sufficiently large graphs. These triples exist of claws \\(K_{1,m}\\) and of two additional graphs whose figures are illustrated in the paper.   The first result (Theorem 2.1) is the introduction of a fifth such triple containing the claw \\(K_{1,3}\\) and further two graphs are sketched. The proof of this result is a very extensive one; the authors need 17 claims.   In a further result (Theorem 3.1) a characterization of the triples of subgraphs that imply traceability when they are forbidden is given, and the authors show that these five families are all such families.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1301658$DFC4C183-9A0A-4BEF-B795-F1602D112A9E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301658$56D5C238-8516-4B3D-8C05-2F0EA915866D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301658$F529A988-65B5-4C3B-B88F-A03011B69488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301658$34CD01F7-4F19-4CBB-ACCB-E25FD90D3855","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3ba2bff9b56f84327d26775201d67a42dc490565","datavalue":{"value":"1334480","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301658$3F348DFA-9005-4049-8A0D-F405844F6084","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"640943ae68953f5cbc0c6fedc31dccbdcc398bd9","datavalue":{"value":"families of forbidden subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1301658$4D3FBCA5-1AA5-4111-88E5-3BBB0EA4F030","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b064239038ee1a771c75dcf49f01efada6cdd6a","datavalue":{"value":"connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1301658$2252CC94-CCA2-463E-9F05-40AD4A2C85A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"924607da8efe2573a9e8496cc49b2d127a27106e","datavalue":{"value":"traceability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1301658$C1278493-B2D5-495D-9414-43029173967A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c89639778a113cbe54a2efcba7f98ccd79f62275","datavalue":{"value":"characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1301658$0108D7B3-F9CE-4385-AFFE-2FE3AB8B9CEF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31cef456e8646accdc28b523a232a52220366047","datavalue":{"value":{"entity-type":"item","numeric-id":593309,"id":"Q593309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301658$1A6AE8E4-6A88-4006-AA71-682B18B48EA3","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":"Q1301658$3E0F63A1-8605-44E6-94E2-71397CCBCD6E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a305482ce08ddf23fda29be6c489473ce73971c","datavalue":{"value":{"entity-type":"item","numeric-id":3918148,"id":"Q3918148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301658$346305E3-D474-4A46-A3E6-433E1A0D9CCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"072e3bfe7ab4b00d00c8edecc86703e8254664dd","datavalue":{"value":{"entity-type":"item","numeric-id":1367026,"id":"Q1367026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301658$E4147E8D-A983-4A33-A20A-383C0CFE8CF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a43088228ae2c164b7d062cc12f5aaa66f79e78d","datavalue":{"value":{"entity-type":"item","numeric-id":3992558,"id":"Q3992558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301658$E25722DD-7C98-4012-B0FF-A54F0FB51A19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1144b0cdfaaf14cf50ee7f109322bc477abe5a27","datavalue":{"value":{"entity-type":"item","numeric-id":3838229,"id":"Q3838229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301658$866E624F-9AC0-41D2-B69A-E525158E2100","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc598655af90475991ead6056913cc64dee97b40","datavalue":{"value":{"entity-type":"item","numeric-id":1584364,"id":"Q1584364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301658$BC6CCB38-F911-4F5F-853C-34E68BB2D260","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7363ea36466e05a1563486052c8141b433be97f0","datavalue":{"value":{"entity-type":"item","numeric-id":3320427,"id":"Q3320427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1301658$EC6E7043-9B93-421F-A0BB-CB5F79BCC520","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1d4a072e527c9fbba9fb6f607e4ea4510f8c4442","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(99)00021-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1301658$01E3899F-C752-4E7B-9DB5-DB09F9CD0613","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"db68fb2408e9c201dd593482a3cedea20c7bde48","datavalue":{"value":"W2109252973","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1301658$91A253A6-179B-4E07-9DA6-DDCEA42AD8A8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6afcb0bb9db34867b10512c5b2a260692e827a8","datavalue":{"value":{"entity-type":"item","numeric-id":1584364,"id":"Q1584364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d0dddb15c06168bc61fbf5e273fa2d4c9176f2d","datavalue":{"value":{"amount":"+0.9301040172576904","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":"Q1301658$00F1780A-EAD2-4847-9266-5B1CFA9A2E42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d665179aca0d5e4e400fedc380bed9c379185849","datavalue":{"value":{"entity-type":"item","numeric-id":3838229,"id":"Q3838229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9ff616026562cefd04a02e829483ffffa74a570","datavalue":{"value":{"amount":"+0.9268506169319152","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":"Q1301658$BD47CCB2-719B-45B0-89B4-C08FFB6D1D20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12191f2567b5e61df29e2716355aab2b139497e7","datavalue":{"value":{"entity-type":"item","numeric-id":3413521,"id":"Q3413521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37217aa3e40e372508b0a3ffc474675a2d46a69a","datavalue":{"value":{"amount":"+0.8376302719116211","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":"Q1301658$2A8C7C58-7B64-4D79-B2F1-8B983AF15D69","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Forbidden triples and traceability: A characterization","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Forbidden_triples_and_traceability:_A_characterization"}}}}}