{"entities":{"Q1763347":{"pageid":1774089,"ns":120,"title":"Item:Q1763347","lastrevid":48417139,"modified":"2026-01-04T16:14:15Z","type":"item","id":"Q1763347","labels":{"en":{"language":"en","value":"Path partitions and \\(P_{n}\\)-free sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2136227"}},"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":"Q1763347$4F56B4AD-F303-4578-B007-F4FDCE664681","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"431841b30cf92871a756942cb2b05630d7eeb4e0","datavalue":{"value":{"text":"Path partitions and \\(P_{n}\\)-free sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1763347$EA8460E0-34C2-4DBA-BEED-A61D5C36AF4F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"24ac2f7e40194e62e87484a44b747de3f0360d62","datavalue":{"value":"1056.05085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1763347$5FEC57C4-4B73-4208-9EFF-108599B093F2","rank":"normal"}],"P16":[{"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":"Q1763347$8160A2E8-98AC-47FE-909E-C72674851F6F","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":"Q1763347$8EFDB055-A8FC-4139-ABD2-D7D2A1CE12DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d431475caa2a841442085475fc70dfe1890287e9","datavalue":{"value":{"entity-type":"item","numeric-id":540047,"id":"Q540047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763347$5666510E-33DE-401B-827F-E746A080E751","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":"Q1763347$7968D459-CDA0-42C3-87F7-7A33E7171037","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e6fd9f57da46494686492c936ca92ef875382ca4","datavalue":{"value":{"time":"+2005-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":"Q1763347$E8ADB4A3-8BD5-4D35-AF01-BEF6A26EC35D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bb1e354e5d2325b96cf98255e1f188048a5c483a","datavalue":{"value":"The detour order \\(\\tau(G)\\) of a graph \\(G\\) is the number of vertices of a longest path of \\(G\\). If \\(S\\) is a subset of vertices of a graph \\(G\\) such that the graph induced by \\(S\\) has detour order at most \\(n\\), then \\(S\\) is called a \\(P_{n+1}\\)-free set in \\(G\\). The path partition conjecture can be stated as follows: For any graph \\(G\\) and any positive integer \\(n<\\tau(G)\\), there exists a \\(P_{n+1}\\)-free set \\(S\\) in \\(G\\) such that \\(\\tau(G-S)\\leq\\tau(G)-n\\). In Theorem 2.1 the authors prove: Let \\(G\\) be a graph and \\(n\\) an integer with \\(2\\leq n<\\tau(G)\\). If \\(X\\) is a maximal \\(P_{n+1}\\)-free set in \\(G\\), then \\(\\tau(G-X)\\leq\\tau(G)-\\frac{2}{3}(n+1)\\). In addition, they show that if the graph \\(G\\) has no cycle of length less than \\(n\\) or greater than \\(\\tau(G)-n+2\\), then \\(\\tau(G-X)\\leq\\tau(G)-n\\) for every maximal \\(P_{n+1}\\)-free set in \\(G\\). As a corollary of the latter result, the authors prove the path partition conjecture for the special class of connected and weakly pancyclic graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1763347$EB7C0E6D-71AB-4146-9FD8-FB30427C2C4E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2a65d3702174a536f0cf916db67d42643a023895","datavalue":{"value":{"entity-type":"item","numeric-id":186197,"id":"Q186197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763347$CC63E55C-37B0-4149-844F-A5E662B14AED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1763347$C037F8FE-B81A-4F23-95A9-C4F40FD95B22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1763347$30E3421B-D6C3-43F5-B286-40527A6ECF1C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1b4ced3694dedc7aba888fe28db74fb553b94362","datavalue":{"value":"2136227","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1763347$028C04C8-0EB1-4ACE-B11B-5A464CB40788","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ebc22d8187ea672fec2c0fc855212abe29ca422","datavalue":{"value":"longest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1763347$2123E5DF-3F43-4AF1-85BB-392AF96B1009","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47c4276bf1e1be1027218b648661d21842d9a6f5","datavalue":{"value":"detour","type":"string"},"datatype":"string"},"type":"statement","id":"Q1763347$74E87F66-5DC7-454A-B508-23354DC0E319","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca3a7448755b7a50ac3116645c7263a056e331af","datavalue":{"value":"vertex partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1763347$FA5DBB60-8332-4384-BCEB-E4D0E3B1C025","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":"Q1763347$6C096C76-558B-4E1A-8AAC-0605986718FB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"43a8c2ecb9c1932441bc599f397ccb877dbe2bcc","datavalue":{"value":"https://doi.org/10.1016/j.disc.2004.07.012","type":"string"},"datatype":"url"},"type":"statement","id":"Q1763347$960DCDA3-42B9-4423-A5CE-9DA21F1EB979","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b7b764679b915d5277fd743bcfa389f7a1fbdc18","datavalue":{"value":"W2140959314","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1763347$285B0C54-728B-4156-922C-C8C00EF623F1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf199cfe008869511237b75edf119c1e10c4fe32","datavalue":{"value":{"entity-type":"item","numeric-id":4209931,"id":"Q4209931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763347$7F783757-9B45-46A3-BDBD-133DFC691A2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"456e8f884f7025cbd4b7d05dc08a5231888d66ed","datavalue":{"value":{"entity-type":"item","numeric-id":4222386,"id":"Q4222386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763347$17299620-04A7-4B11-916F-12A77A1B1C1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac49bc8c91f876b808e0df574183b16063498794","datavalue":{"value":{"entity-type":"item","numeric-id":4210673,"id":"Q4210673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763347$34172195-629A-45C8-AEE9-46DB17324619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63e67aa2eed37c43efa616fc2f14b77fbd046898","datavalue":{"value":{"entity-type":"item","numeric-id":4943521,"id":"Q4943521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763347$F31E1B06-0797-4818-A38E-B6633909B946","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcf4c943553bf0d450bc5fc44ca4977a66591531","datavalue":{"value":{"entity-type":"item","numeric-id":787160,"id":"Q787160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763347$FDE788AC-BFB2-4FF5-970C-4B7563E30ABF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2938a8fc965fd5d6cf2cc7e160b41d494b9d9eb","datavalue":{"value":{"entity-type":"item","numeric-id":5554157,"id":"Q5554157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763347$DD757C45-47D3-4F2C-AC4C-03D564128FAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74074974e02935f8f5ecb942cc6fe70f08b746ea","datavalue":{"value":{"entity-type":"item","numeric-id":5530470,"id":"Q5530470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763347$DD37EF95-1666-43D8-8314-AE267326A2AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c79a83cb7b25d2242a5483bf8d753dbc190bea4b","datavalue":{"value":{"entity-type":"item","numeric-id":3701351,"id":"Q3701351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763347$B0EF799D-81E8-4E84-88FF-F376277FB770","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72726adcefd20ecdeea80ec29373f23b2f0da4b5","datavalue":{"value":{"entity-type":"item","numeric-id":4715286,"id":"Q4715286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763347$E77F50A9-49E6-489A-8D14-B68D5C47984F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8bc2ae23bb13dbcaf7cb2eeb2f5caf3d7d5489","datavalue":{"value":{"entity-type":"item","numeric-id":3661610,"id":"Q3661610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1763347$39725CED-8FF5-4379-8EA2-12788D5CA3D9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fff832d84191ed2944aee5315eceef7da1bbfd8d","datavalue":{"value":"10.1016/J.DISC.2004.07.012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1763347$4D270630-C0CB-41BE-B648-3F0D446311ED","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"500cd9dac3556b80c38b91862c3b32fe7309a491","datavalue":{"value":{"entity-type":"item","numeric-id":2571291,"id":"Q2571291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bbe0d08a9c35e0e66271daf098df28c960c5ac3","datavalue":{"value":{"amount":"+0.8739495873451233","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":"Q1763347$82523AF6-E0E3-4579-B4EE-2918F29D4A94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a87364930c72a72a912e8a0827d1150c564d11b2","datavalue":{"value":{"entity-type":"item","numeric-id":878616,"id":"Q878616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a75b17db1865c8fa019c64bc46297629ed0dc097","datavalue":{"value":{"amount":"+0.8655660152435303","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":"Q1763347$7D5A2610-ABF9-43EE-92AF-F050E2E62BC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"544f0c95ba5b78aa1e7a223d36e6a30ffccacb85","datavalue":{"value":{"entity-type":"item","numeric-id":3166152,"id":"Q3166152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2f9333cfacc16faf6ca3fe42108c5327d6947e1","datavalue":{"value":{"amount":"+0.848479688167572","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":"Q1763347$E35298E8-AB2B-4022-AE99-202A28FFAA3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84fcc3d072096381fcbd17252eb40d8a517c8804","datavalue":{"value":{"entity-type":"item","numeric-id":5488344,"id":"Q5488344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"099e73e3a9ef53b1767c4c7c694a4ff88d98a6f8","datavalue":{"value":{"amount":"+0.8274983167648315","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":"Q1763347$A15EC30E-EB8C-4B4D-953A-DF02E1799910","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54eb57a8d42239b56535fc4b3ff67afd9ecb1c15","datavalue":{"value":{"entity-type":"item","numeric-id":4943521,"id":"Q4943521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1836b33d90b7940a609eb7f4058392b6fb6cd7e","datavalue":{"value":{"amount":"+0.8158766031265259","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":"Q1763347$0197F922-E2BD-4345-B7D1-F39F53D26D81","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1763347","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1763347"}}}}}