{"entities":{"Q2415079":{"pageid":2425822,"ns":120,"title":"Item:Q2415079","lastrevid":57900750,"modified":"2026-04-03T00:33:09Z","type":"item","id":"Q2415079","labels":{"en":{"language":"en","value":"Vizing's 2-factor conjecture involving toughness and maximum degree conditions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7056824"}},"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":"Q2415079$1BA7F7A5-D506-4851-9173-67BABA0E105D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"02130bece63512f41d41c393efce9f060eedc870","datavalue":{"value":{"text":"Vizing's 2-factor conjecture involving toughness and maximum degree conditions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2415079$30C2EB8E-789D-475F-9CA6-0E0674800CD5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3c3b8e65184b01dc565765c5af7111279a86b98a","datavalue":{"value":"1412.05045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2415079$36E08ACE-6B91-4E3D-97FC-E29A8A01F8CC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"54fdf92ddff75d4f72f066be987623ffd548bd6b","datavalue":{"value":{"entity-type":"item","numeric-id":1069179,"id":"Q1069179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$8670F59B-202E-4556-89E9-82163C793D69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f312e00acc1947270ff9dd670df2a632a917a4a3","datavalue":{"value":{"entity-type":"item","numeric-id":463283,"id":"Q463283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$DE266D6C-569C-44F9-9D53-DA49C1E57768","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$8148905F-383C-4474-BD42-E4EFE1362919","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"76aea2b75495bec6f97e62ffc31f2b341286902a","datavalue":{"value":{"time":"+2019-05-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2415079$ED52C62B-16E2-4105-A4DF-D6723828CA5D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a0fddacec66d9de116c883a4ebb99da4a032cf80","datavalue":{"value":"https://arxiv.org/abs/1709.02241","type":"string"},"datatype":"url"},"type":"statement","id":"Q2415079$07DD50DF-6869-4A91-9DAA-FA7569EB6E02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"ee07ad974e412db9b381b5befc77c9efc3902734","datavalue":{"value":"https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i2p17","type":"string"},"datatype":"url"},"type":"statement","id":"Q2415079$D3F1E6FC-467C-4BD6-A3A4-9E3E77AD89DD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0be28c3973824fcd70dc983e5d7bbb1ae522b278","datavalue":{"value":"Summary: Let \\(G\\) be a simple graph, and let \\(\\Delta(G)\\) and \\(\\chi'(G)\\) denote the maximum degree and chromatic index of \\(G\\), respectively. Vizing proved that \\(\\chi'(G)=\\Delta(G)\\) or \\(\\chi'(G)=\\Delta(G)+1\\). We say \\(G\\) is \\(\\Delta\\)-critical if \\(\\chi'(G)=\\Delta(G)+1\\) and \\(\\chi'(H)<\\chi'(G)\\) for every proper subgraph \\(H\\) of \\(G\\). In 1968, Vizing conjectured that if \\(G\\) is a \\(\\Delta\\)-critical graph, then \\(G\\) has a 2-factor. Let \\(G\\) be an \\(n\\)-vertex \\(\\Delta\\)-critical graph. It was proved that if \\(\\Delta(G)\\ge n/2\\), then \\(G\\) has a 2-factor; and that if \\(\\Delta(G)\\ge 2n/3+13\\), then \\(G\\) has a hamiltonian cycle, and thus a 2-factor. It is well known that every 2-tough graph with at least three vertices has a 2-factor. We investigate the existence of a 2-factor in a \\(\\Delta\\)-critical graph under ``moderate'' given toughness and maximum degree conditions. In particular, we show that if \\(G\\) is an \\(n\\)-vertex \\(\\Delta\\)-critical graph with toughness at least 3/2 and with maximum degree at least \\(n/3\\), then \\(G\\) has a 2-factor. We also construct a family of graphs that have order \\(n\\), maximum degree \\(n-1\\), toughness at least \\(3/2\\), but have no 2-factor. This implies that the \\(\\Delta\\)-criticality in the result is needed. In addition, we develop new techniques in proving the existence of 2-factors in graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2415079$DCB43659-6E66-4CB8-9328-D55563F03F05","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2415079$FE99F099-5CD2-4C69-A789-C9DB6DFA93B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2415079$A8FB6E77-189E-49DA-B285-35D29C0AC02D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2415079$6AECE966-817D-41D2-9A9E-CCE483747CE3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ec77d4509a869c1d146ca10254486726e9232b56","datavalue":{"value":"7056824","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2415079$DF037FDF-75DE-4701-8690-B2FDFEC3F243","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":"Q2415079$0059030D-C0E6-49E8-9C27-6237463FC313","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"96722e42c882d5d3cac2c189923af429d6d11e9c","datavalue":{"value":{"entity-type":"item","numeric-id":3174237,"id":"Q3174237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$38EF0984-8E66-4EF3-BBDA-CEDD93297F1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d50263b65adf5166e0e6228d3239913e2666a3f3","datavalue":{"value":{"entity-type":"item","numeric-id":4487665,"id":"Q4487665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$75B925D1-D279-4EEB-8BB4-3A0CCDE0D3B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cec27c91eb3290967ec351fa393f93ca1c0bed7f","datavalue":{"value":{"entity-type":"item","numeric-id":1999729,"id":"Q1999729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$63ED6A11-7ABF-4881-9A78-FBEF11AE7A8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5370f07c6277eeb7b24314b2debe5dc034ed30cf","datavalue":{"value":{"entity-type":"item","numeric-id":5408593,"id":"Q5408593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$96F2B521-0568-4CDE-B918-CA4371171240","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"138b551314cbf5ac1d187b278853f9b452ffb24c","datavalue":{"value":{"entity-type":"item","numeric-id":4596325,"id":"Q4596325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$FE9BF267-F0CC-4DFB-B358-1D5DBFFD09AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8788f05ae82cfbd0ae01fb3681f4ca02a719c218","datavalue":{"value":{"entity-type":"item","numeric-id":3731636,"id":"Q3731636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$8B61AEF0-7AC7-4A58-86F0-61AB89AAC1CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9a3777cda8907bf69abf40ec8cc73a538cc6133","datavalue":{"value":{"entity-type":"item","numeric-id":4458595,"id":"Q4458595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$A5E2FF64-220D-4D4A-89E7-CBDFF60D948F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$6C614F48-A53A-4355-86DF-56506908331E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5770d420e10125d548a31be8eab92edf86db1b3c","datavalue":{"value":{"entity-type":"item","numeric-id":343761,"id":"Q343761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$F8D6C1AC-A295-4074-B1A0-970F36361758","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d47f02cbae07aafe5dc991d14f6641606dd6d105","datavalue":{"value":{"entity-type":"item","numeric-id":2502907,"id":"Q2502907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$1AC44F9B-6863-4B5B-98D6-48E2CB68B33B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d90156675d7dfa055270b5df8563c5b68b05d86","datavalue":{"value":{"entity-type":"item","numeric-id":3096957,"id":"Q3096957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$2CD62064-5FC8-4265-8EAC-ACF627AC9B71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7bdc4f871e92628283759a36d8e8c5d0fd03785","datavalue":{"value":{"entity-type":"item","numeric-id":5325954,"id":"Q5325954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$029D7C8D-8D96-4467-8375-745269644AB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0f4e7516daa6d4014d6dbd7077864aea96730aa","datavalue":{"value":{"entity-type":"item","numeric-id":5826303,"id":"Q5826303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$670A51B9-573F-4D0A-BBA3-4B11B381DC38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f49ebc6ffd383a2cbc88d38dc759465c647e27a","datavalue":{"value":{"entity-type":"item","numeric-id":5550921,"id":"Q5550921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$BB312548-5B09-4527-B86C-E99C7BE1007C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87c8ff4fc6f711a607a536b6572a8daeb1f68437","datavalue":{"value":{"entity-type":"item","numeric-id":5558480,"id":"Q5558480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$D0DE332F-3905-4007-9A49-AF0F4788E0C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d7689ee794d05f267735d01d099a85da834d533","datavalue":{"value":{"entity-type":"item","numeric-id":5564127,"id":"Q5564127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$E837D6E9-BBC8-48BE-9283-A77C9AF5E6DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e3d300de9fd7d77cad42a4fa158ac301d9f5eb6","datavalue":{"value":{"entity-type":"item","numeric-id":3081307,"id":"Q3081307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415079$E21F4097-C1FF-49F3-AD43-046DFB03D4D3","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"2f72e55d40b725eb684a8ac92e7ae2045a8fe98a","datavalue":{"value":"bafkreicszbwoxwrisdv3njrylikf2iawq46mrom7nyqohrvo7cki74fk3e","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2415079$44C0D70D-2BFB-4F6C-A689-704276729404","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47601a0431c0f8ded0a3085c6353f7561f64968b","datavalue":{"value":{"entity-type":"item","numeric-id":4596325,"id":"Q4596325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92b6a36532c48d87606b654f238b07429789d558","datavalue":{"value":{"amount":"+0.9389621615409852","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":"Q2415079$FBD7FBB2-F6B3-4541-A426-0C2025C29C94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0fe83483fe18d895843f60fc1c39e3b83f8c408","datavalue":{"value":{"entity-type":"item","numeric-id":5325954,"id":"Q5325954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35603c423f3731b8bd8c24b5787bf766b134f524","datavalue":{"value":{"amount":"+0.8857033252716064","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":"Q2415079$D57564D6-12DB-4AB5-B440-49ADCD8334B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b92c6d3860d0b8022b4ec4d850ceba1e3de3b32","datavalue":{"value":{"entity-type":"item","numeric-id":2227997,"id":"Q2227997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75171cd0abae0893522f36d5613624486634431e","datavalue":{"value":{"amount":"+0.8467849493026733","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":"Q2415079$AB1421C6-5D14-47F8-935B-5C40F9F3EFDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bf64ef06c89ddf491799787fc97e55db9b3270d","datavalue":{"value":{"entity-type":"item","numeric-id":4693341,"id":"Q4693341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"601dde2f487fe40571860a3ceeca9770b704f8df","datavalue":{"value":{"amount":"+0.8200292587280273","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":"Q2415079$02D3B974-3A44-465C-A071-C3086D3F3141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35ca37c76520031e0897bdc3a844c4231864cd79","datavalue":{"value":{"entity-type":"item","numeric-id":1299991,"id":"Q1299991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fe252473e8b1d1ce71924a79a1f7a5ec597df4f","datavalue":{"value":{"amount":"+0.8196326494216919","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":"Q2415079$A4F4C19A-78EC-447B-8EC3-EB5621FEEE7C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2415079","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2415079"}}}}}