{"entities":{"Q414645":{"pageid":416412,"ns":120,"title":"Item:Q414645","lastrevid":61782990,"modified":"2026-04-11T01:38:22Z","type":"item","id":"Q414645","labels":{"en":{"language":"en","value":"Minimum \\(H\\)-decompositions of graphs: edge-critical case"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6033281"}},"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":"Q414645$A5456FF9-71B7-4EB4-B44F-CF3F447787E1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bcabab730c78b6eb4ac91948f1c984f3ceaf57fe","datavalue":{"value":{"text":"Minimum \\(H\\)-decompositions of graphs: edge-critical case","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q414645$9A12E77F-E060-4F87-9DAC-BE3BB6766833","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0a4613edb661635ffa56da187b6db293999600c3","datavalue":{"value":"1250.05089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q414645$9AF33505-B83D-419B-905A-B06049FC236D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"551cfc6ea2851ae6d670f274ea58e3dc4b6b30ce","datavalue":{"value":{"entity-type":"item","numeric-id":414644,"id":"Q414644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$6552F312-65C2-430D-83D9-852C13708351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2532270aa021c282902fb16beb1092e301044e83","datavalue":{"value":{"entity-type":"item","numeric-id":290807,"id":"Q290807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$1FB19BAB-8691-42A8-BAB2-D0B896ED935A","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":"Q414645$D224A7BF-7FFF-4357-835E-2BEB70C10EF0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ebad7c55eb31a5728be157b82e80bb61556d824d","datavalue":{"value":{"time":"+2012-05-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":"Q414645$5A4A4D56-96F6-4692-908B-30788269D0FD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ee132732f475ab3c7ca9e2d15f46252fb557c4df","datavalue":{"value":"Given a graph \\(H\\) let \\(\\phi_{H}(n)\\) denote the maximum number of parts that are needed to partition the edge set of any graph on \\(n\\) vertices such that every member of the partition is either a single edge or isomorphic to \\(H\\). Furthermore, let \\(ex(n,H)\\) denote the maximum size of a graph on \\(n\\) vertices not containing \\(H\\) as a subgraph. \\textit{O. Pikhurko} and \\textit{T. Sousa} [``Minimum \\(H\\)-decompositions of graphs,'' J. Comb. Theory, Ser. B 97, No.\\,6, 1041--1055 (2007; Zbl 1125.05085)] conjectured that \\(\\phi_{H}(n)=ex(n,H)\\) for \\(\\chi(H) \\geq 3\\) and all sufficiently large \\(n\\). Sousa verified the conjecture for clique extensions of order \\(r \\geq 4\\) (\\(n \\geq r\\)) [\\textit{T. Sousa}, ``Decompositions of graphs into a given clique-extension,'' Ars Comb. 100, 465--472 (2011; Zbl 1265.05313)], the cycles of length 5 (\\(n \\geq 6\\)) [\\textit{T. Sousa}, ``Decompositions of graphs into 5-cycles and other small graphs,'' Electron. J. Comb. 12, No. 1, Research paper 49 (2005; Zbl 1079.05044)] and 7 (\\(n \\geq 10\\)) [\\textit{T. Sousa}, ``Decomposition of graphs into cycles of length seven and single edges,'' Ars Comb. (to appear)]. In this paper, the authors verify the conjecture for all edge-critical graphs. They also show that the graphs maximizing \\(\\phi_{H}(n)\\) are \\((\\chi(H)-1)\\)-partite Tur\u00e1n graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q414645$956D6853-D307-4591-BD90-AD7235FC7CCF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a45b400d22190ce8d9d8376830240adc5a55cd78","datavalue":{"value":{"entity-type":"item","numeric-id":367043,"id":"Q367043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$2FD78D4D-CB08-42B4-843A-E3A8CD7CB7BA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q414645$51EE04F3-1EE8-4845-9A8C-70394F2F5016","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q414645$14F05896-61B3-438B-929C-03FBB9E85DAD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8d0ac7e699410915b4519042c4fbe77a09281f8f","datavalue":{"value":"6033281","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q414645$C0F7C7D1-EF1D-4627-8D67-1F73897E7350","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d73af52c8be4cc62e4af3d3be7afe8738385822a","datavalue":{"value":"Graph decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q414645$E8B3A077-E2BA-4703-A871-FFC9820D0E39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"015facd14939fbbd3f055f3f4a61e275710965e3","datavalue":{"value":"Edge-critical","type":"string"},"datatype":"string"},"type":"statement","id":"Q414645$C3F875FB-1902-46A6-9F84-F5F56953BCC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78f2f08a63b334bc1ecceb3db8198e8441e051d9","datavalue":{"value":"Tur\u00e1n graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q414645$C46BDDCC-F234-464D-A4BE-28A589B20D78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72ddf7d6b0699009f43d5b480b22628fdcec11dd","datavalue":{"value":"Stability approach","type":"string"},"datatype":"string"},"type":"statement","id":"Q414645$C95CF074-7ECD-4A62-A0BD-4C4052AC3207","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":"Q414645$CCC6EF7A-3E71-4283-84E1-FA6872D19A78","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e4bb5540561304ca032d4adef09741f61e0b60a1","datavalue":{"value":"https://doi.org/10.1016/j.jctb.2011.10.004","type":"string"},"datatype":"url"},"type":"statement","id":"Q414645$AD5D8548-01C3-45B4-85D2-FF528256AC87","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"54c985a596691e50bfbf5e43dc3fa06278343d76","datavalue":{"value":"W2018719884","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q414645$A76F86EE-2593-4B4E-B8AB-61B32A0B911B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c62594ef1ea9514c3144b6b09c5975a99cbda73f","datavalue":{"value":{"entity-type":"item","numeric-id":4088852,"id":"Q4088852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$94620B4E-37B0-4890-8753-D60C27D84AA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77d6452e54e5e6983bfa6dba10e55824db2fd929","datavalue":{"value":{"entity-type":"item","numeric-id":5814290,"id":"Q5814290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$20EF8EAE-1636-4EE6-A4F0-198E24B391EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72416fa7a6ee3d06ea820979ef98e6dfd2623198","datavalue":{"value":{"entity-type":"item","numeric-id":5544083,"id":"Q5544083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$FB29E292-357C-4ECF-A945-7ADAC188E528","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c867b0d18c5229cdc2ec1ab76ab40ab92d3fd53e","datavalue":{"value":{"entity-type":"item","numeric-id":5512009,"id":"Q5512009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$CCBD42D3-608A-4520-A819-4F32F10D6DC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b79004eec82002fc898d57feecbac5016d092acd","datavalue":{"value":{"entity-type":"item","numeric-id":5842850,"id":"Q5842850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$40DA1AAA-BE74-475E-ACE3-099C7AC4D5D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06fd991c17ccc401b4e085e826577f401894b092","datavalue":{"value":{"entity-type":"item","numeric-id":2384810,"id":"Q2384810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$10F0A570-4B23-4116-94A6-6885E304010A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0646bbc4e3baa681a19e8c502a0cba327147b2f","datavalue":{"value":{"entity-type":"item","numeric-id":805633,"id":"Q805633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$39E4F81A-9AD7-4219-A294-B1011C8F76E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"887ce430b000ffd8813e06446b140ace91a67a26","datavalue":{"value":{"entity-type":"item","numeric-id":5548826,"id":"Q5548826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$BF24142D-8429-4908-A342-FEA7A6694463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"458831b6f300e3ec829c94a19f548f31b8aae2e2","datavalue":{"value":{"entity-type":"item","numeric-id":2571292,"id":"Q2571292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$A06EC8C6-5A64-4D96-9906-0E95C31FC688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f747938869143a705af03bae0319af249f7e1e0","datavalue":{"value":{"entity-type":"item","numeric-id":3166469,"id":"Q3166469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$14554D34-42E2-45F9-84E9-AF0709160C2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82d171f480bb57c19b51e0460359f6db2a0ba123","datavalue":{"value":{"entity-type":"item","numeric-id":2804806,"id":"Q2804806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$333E0E75-7F01-46FE-8A58-D6A3591BD7A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"922598857b64c682415741da5fd4eb7cb848d71b","datavalue":{"value":{"entity-type":"item","numeric-id":4200109,"id":"Q4200109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414645$1EBFE001-07A4-4919-8428-09D908842E45","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a03ad26a9b23fde4b0b8e647991b99bb5a7cc398","datavalue":{"value":"10.1016/J.JCTB.2011.10.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q414645$5620D52D-1212-401C-8FA9-DD6BDED5E74F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aaf41333d321cf8f3881769430ed6a7800f55fdb","datavalue":{"value":{"entity-type":"item","numeric-id":740649,"id":"Q740649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b57945ae0300c483cc496b4574b7a0d8160a651","datavalue":{"value":{"amount":"+0.8706717491149902","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":"Q414645$DB7003F5-8165-454B-8DE0-EA501CFAFD6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61a971053ac1932081a50a2bd7f5fe45dfbbe098","datavalue":{"value":{"entity-type":"item","numeric-id":2384810,"id":"Q2384810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7b575aaaa1e72ab58a27cfa6f845f92ca6d3874","datavalue":{"value":{"amount":"+0.8588957786560059","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":"Q414645$319D67FA-2817-4570-9A57-9FA30FA12547","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fbc249b262c6a53cb17b94f5159de6d0425713d","datavalue":{"value":{"entity-type":"item","numeric-id":5272925,"id":"Q5272925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"063f719e889edab45d6104651600ccaf3b4bf25e","datavalue":{"value":{"amount":"+0.8415802717208862","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":"Q414645$2BEE9C31-4188-42B1-8117-886C1C875AF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c3331e079e5fb6aa83e09c81f7eae3c8e1d28ab","datavalue":{"value":{"entity-type":"item","numeric-id":2804806,"id":"Q2804806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abaec2f446f32e13c22c8d4e7d4abe888aa792b3","datavalue":{"value":{"amount":"+0.8355681300163269","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":"Q414645$73C22A43-C04B-4526-A8C8-673963EDE773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9dcdc3d58b61edc51648948d2e4511642e8e470","datavalue":{"value":{"entity-type":"item","numeric-id":4604014,"id":"Q4604014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9ece18f5868326a7c2667b6b36344dac78ceb9d","datavalue":{"value":{"amount":"+0.8316617012023926","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":"Q414645$81CF78DF-4BDE-45A4-BD50-5E3F4DF3E6D4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimum \\(H\\)-decompositions of graphs: edge-critical case","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimum_%5C(H%5C)-decompositions_of_graphs:_edge-critical_case"}}}}}