{"entities":{"Q1877673":{"pageid":1888415,"ns":120,"title":"Item:Q1877673","lastrevid":69174618,"modified":"2026-04-13T05:16:12Z","type":"item","id":"Q1877673","labels":{"en":{"language":"en","value":"Graphs with not all possible path-kernels"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2092842"}},"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":"Q1877673$C8447572-FCBC-46BB-919E-817E80BC9EF2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c3a4303ab5116619a068181e262e4d2e54333189","datavalue":{"value":{"text":"Graphs with not all possible path-kernels","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1877673$B35D0683-03A1-490A-86DF-57D147195637","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4ddb1c90d534c248e1637bb6f36ed931bdbb5b5f","datavalue":{"value":"1066.05107","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1877673$EB4782F2-6C0C-4A51-AFDB-F2BB8CB90916","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aec857263cee52fe850f36c12f5157e5c8f0a013","datavalue":{"value":{"entity-type":"item","numeric-id":228790,"id":"Q228790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877673$B33D316E-27B2-4C60-90F3-395929767AA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0352d786be82754ed778f0a47e4579bea78fe5f7","datavalue":{"value":{"entity-type":"item","numeric-id":189706,"id":"Q189706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877673$80EF08A2-0AEC-4A2C-9E5C-458D45C53B50","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":"Q1877673$50BE0684-768B-49B8-91E4-ED134249C2E5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dad9e6929b84d2aa86589bcc6be2d26ada8b5576","datavalue":{"value":{"time":"+2004-08-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1877673$A0F348F7-E07F-4AFB-8668-C2464C91A7E6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f9fbbd5c588d6eb0b59a2811898482f60a2e8e77","datavalue":{"value":"Let \\(\\tau(G)\\) denote the number of vertices in a longest path in a graph \\(G\\). The path partition conjecture states that for every graph \\(G\\) and for all integers \\(a\\) and \\(b\\) with \\(a+ b= \\tau(G)\\) there is a partition \\(\\{A, B\\}\\) of the vertex set of \\(G\\) such that \\(\\tau(G[A])\\leq a\\) and \\(\\tau(G[B])\\leq b\\). Even stronger is the following conjecture by \\textit{I. Broere}, \\textit{P. Hajnal} and \\textit{P. Mih\u00f3k} [Discuss. Math., Graph Theory 17, No. 2, 311--313 (1997; Zbl 0906.05059)], stating that for every graph \\(G\\) and for every integer \\(k\\), \\(2\\leq k\\leq \\tau(G)\\), there is a partition \\(\\{A, B\\}\\) of the vertex set of \\(G\\) such that \\(\\tau(G[A])= k- 1\\) and each vertex in \\(B\\) is adjacent to an end vertex of a longest path (on \\(k- 1\\) vertices) in \\(G[A]\\). The paper disproves Broere, Hajnal and Mih\u00f3k's conjecture by giving a counterexample with 364 vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1877673$8E0E9C85-6D7C-4B0A-AC65-9212073E5935","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0748e85c1b0f40a68146ca2556ec923bb53f58d4","datavalue":{"value":{"entity-type":"item","numeric-id":178604,"id":"Q178604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877673$BF6755D5-5B2F-434D-AA8D-27D59012E82E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1877673$A9C0D5BA-83A1-4D0E-83E1-B58E1DDBA36B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1877673$F3C00E0C-4600-4669-A516-423B34DBECDB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"06981e23a2caf8140b51421e18d015bf3a028cc3","datavalue":{"value":"2092842","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1877673$13FE35D5-C81E-4F5F-A3FC-252714063C85","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a6abd881a56495780aafa106e4ce9af3a9f9fb7","datavalue":{"value":"path partition conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1877673$5871C381-4726-4994-9B81-BD8306772A62","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":"Q1877673$39B2C786-AC54-4763-9415-F11C77B5572F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"988469ef4f19af392dc05b0850250ccb2a8d7605","datavalue":{"value":"https://doi.org/10.1016/j.disc.2004.02.012","type":"string"},"datatype":"url"},"type":"statement","id":"Q1877673$8296CA0F-422E-4B85-8500-A9D4583C1FAB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c0d5a41ff5cf3eba2c28413844accda533b6ef3d","datavalue":{"value":"W2026328547","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1877673$F28CDD7D-D11D-4B85-A590-8ABA2B9D3D5F","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"089f1d9257c4ac5557d4df8e8470946791a33ff9","datavalue":{"value":"Q56926698","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1877673$7EDB4D58-8115-4FA7-85EE-DD1035B0125A","rank":"normal"}],"P223":[{"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":"Q1877673$A4CAB71A-FDAD-4FB4-8AFD-12190D03F3BA","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":"Q1877673$0A3DF5DA-E5CB-4EEB-837B-B56D281B5DC5","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":"Q1877673$CD0D45EB-7C82-4699-A931-0D81C6F467B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0af858721480a2bdaeec78555a9a9ba519525af","datavalue":{"value":{"entity-type":"item","numeric-id":1394359,"id":"Q1394359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1877673$69389F8D-F665-483C-863F-F54AB6A2F153","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ea29f0097961ba153492bd97f424dc42066c4bae","datavalue":{"value":"10.1016/J.DISC.2004.02.012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1877673$C1076241-98C4-4F77-A439-37E0A806B65A","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"9d6ba0f1d7670224753bd489840fbecf9ff646f2","datavalue":{"value":"journals/dm/AldredT04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1877673$177C3A32-FF07-4351-A848-D1D3269A8D3D","rank":"normal"}],"P1643":[{"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":"778101d3566226a532bf1e1340f2190dc19ab0c5","datavalue":{"value":{"amount":"+0.8859381675720215","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":"Q1877673$78D1C09B-707B-438F-82A7-20A883022848","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e343cb0f036408262031d6fc90e5d0631082525","datavalue":{"value":{"entity-type":"item","numeric-id":1025521,"id":"Q1025521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9dc795672c6eefbe4810deb6ba40645558f540e3","datavalue":{"value":{"amount":"+0.8710524439811707","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":"Q1877673$1ECDCF21-2EBB-463E-A044-06C273DDDA3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d57c78236f9a68faefb23b3bc73f6486b8993a00","datavalue":{"value":{"entity-type":"item","numeric-id":4210673,"id":"Q4210673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cd2a5c4bd16f1fb2a72980affb3cecd7023aa67","datavalue":{"value":{"amount":"+0.8375827074050903","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":"Q1877673$A07FE67D-CCF3-49AA-988A-8E668D56C8DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4edfe67f809e0a7d832d902a8f6095e582735849","datavalue":{"value":{"entity-type":"item","numeric-id":1763347,"id":"Q1763347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cd2a5c4bd16f1fb2a72980affb3cecd7023aa67","datavalue":{"value":{"amount":"+0.8375827074050903","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":"Q1877673$5E6FDED0-4CB4-418F-A857-17DE91A37E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5884490dda9e24ffe5f86becc676025b26210e9","datavalue":{"value":{"entity-type":"item","numeric-id":4222386,"id":"Q4222386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f659c6b091d638198b43a80e8b3ed3046c06902","datavalue":{"value":{"amount":"+0.8306878209114075","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":"Q1877673$F7FBCB74-88BA-42C4-84AC-F8CED03BFDD3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graphs with not all possible path-kernels","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graphs_with_not_all_possible_path-kernels"}}}}}