{"entities":{"Q858687":{"pageid":860535,"ns":120,"title":"Item:Q858687","lastrevid":64990074,"modified":"2026-04-11T23:34:35Z","type":"item","id":"Q858687","labels":{"en":{"language":"en","value":"Haj\u00f3s' conjecture for line graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5115325"}},"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":"Q858687$82805DE9-37AB-46AB-9AA3-43BD7D92CCBE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a5f7b9f211a852364863c8a741960750901bd056","datavalue":{"value":{"text":"Haj\u00f3s' conjecture for line graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q858687$F520C144-F926-4B52-9F6F-C13DBA241FF2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a53fde2ae11829ab4640d5a76e7acd60f08acf8f","datavalue":{"value":"1114.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q858687$E6E14933-F428-4EE7-8F06-9161A44AEBCF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q858687$968615A2-7266-41D9-BCD7-6537C545CF1C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8e2bf25ad524fc43d672bc2587bd535911f4f3f0","datavalue":{"value":{"time":"+2007-01-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q858687$128B30AD-4A71-4D8B-ADF9-0A9A3880332D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dabf63da6cdd1237841d632f6e3c92ca7a186359","datavalue":{"value":"G. Haj\u00f3s conjectured (1961) that if a graph has chromatic number \\(k\\), then it contains a subdivision of \\(K_k\\). Counterexamples are known that are line graphs of multigraphs. Here it is proved that if a graph \\(X\\) without multiple edges has maximum valence \\(d\\) and edge-chromatic number \\(d+1\\), then \\(X\\) has a pair of vertices joined by a \\(d\\)-set of edge-disjoint paths. Moreover, the line graph of \\(X\\) satisfies Haj\u00f3s' conjecture.","type":"string"},"datatype":"string"},"type":"statement","id":"Q858687$8271B44E-AE9B-4439-BEFA-47B97384F4C4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q858687$C4509B10-E9FC-4635-AA7A-B692649A7C80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q858687$4BE6EE36-62DC-424E-A588-BE172D518D29","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5d896381687fe400a0e69ab48c441cc2c510b45d","datavalue":{"value":"5115325","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q858687$E246F781-1A0D-48C1-A874-D3C8FA8A0761","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q858687$E6736BD4-4E8D-4357-9AE8-B569B4153E9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7832632c39185d9554b5fc9078d102748d811215","datavalue":{"value":"edge-disjoint paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q858687$36CBB1E9-214A-499A-979A-CD33B9871DC5","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":"Q858687$3601223B-B14F-45BE-B3B1-B84E450FDD8B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2420d8bcf60fc74d0291a3c59f694629f273e260","datavalue":{"value":{"entity-type":"item","numeric-id":426905,"id":"Q426905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q858687$05225444-2865-4B9D-B868-6908EE02B5F6","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":"Q858687$0C0C9CC6-28D8-44D3-92C7-5F57B74A7A31","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"16ca76527b32eb1c0e2b32ce5bf3eaf2eef79263","datavalue":{"value":"https://doi.org/10.1016/j.jctb.2006.03.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q858687$7AD149C4-0938-4E0F-8CF8-4FAB2895D9F1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"43bfaa359d5ed19c64dd39300a3a7dd31bf25738","datavalue":{"value":"W2114892226","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q858687$EA3734D5-B172-45C3-9A6A-54DF95C962FE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q858687$A0ACDDAB-B192-4559-9CF2-6E8270FEC6B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcef069c7dd8076501351c207582d7a61f643ecb","datavalue":{"value":{"entity-type":"item","numeric-id":1249185,"id":"Q1249185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q858687$D0A240DC-44B5-4B67-A6D1-547B172EB043","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d1474ad965005531fc787ddda571bd10843eacd","datavalue":{"value":{"entity-type":"item","numeric-id":3853641,"id":"Q3853641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q858687$E7C02C4F-F543-4F20-91FE-8FD19DDF3824","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f9863f7e8b00102ca98b6ceb0f7c146a10a725cc","datavalue":{"value":"10.1016/J.JCTB.2006.03.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q858687$1CF7CF24-774E-4F23-A880-BBF72342231F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4dbdbe1a98d259f4d392f2b1af7c6aff7664c38","datavalue":{"value":{"entity-type":"item","numeric-id":707025,"id":"Q707025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a96b8f13010f0b5f824669d513eef9985270e85","datavalue":{"value":{"amount":"+0.8199635148048401","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":"Q858687$0939BA94-761A-4838-BBD7-561E3A07796A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b48bbbc7db838c3febe10d5745f2eb9fc3bcd814","datavalue":{"value":{"entity-type":"item","numeric-id":1883296,"id":"Q1883296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3a08743fba321683683fbb43bce4f3cd806eb02","datavalue":{"value":{"amount":"+0.8176542520523071","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":"Q858687$F7EAD8CE-94A0-4EFE-964B-A3D72B308A6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5f98b4bde1a3c7bfb8777a2621604f32d64f5a9","datavalue":{"value":{"entity-type":"item","numeric-id":1835686,"id":"Q1835686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b803215fbb6368a90a0474f3990c34bd434c488","datavalue":{"value":{"amount":"+0.816440999507904","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":"Q858687$38DB29DF-BD98-458E-B40A-9B2A9DE736E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"591cf636b64fd26f3393207ae7bcaaeb56c890ef","datavalue":{"value":{"entity-type":"item","numeric-id":1010682,"id":"Q1010682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b005c86c1c703962517a851989b511c935e91c0c","datavalue":{"value":{"amount":"+0.8022034764289856","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":"Q858687$83E47371-EC43-40C9-BC12-1B031D8B3801","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa591224c7ab044492ba6bc1cee995904d40b84d","datavalue":{"value":{"entity-type":"item","numeric-id":1970708,"id":"Q1970708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70b9ff4e6fceb3b9e4ad5019367f762803ad226f","datavalue":{"value":{"amount":"+0.7972437739372253","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":"Q858687$8277BBE8-67B6-44FD-AB3A-7B76F4482E15","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Haj\u00f3s' conjecture for line graphs","badges":[]}}}}}