{"entities":{"Q1085185":{"pageid":1095937,"ns":120,"title":"Item:Q1085185","lastrevid":42862684,"modified":"2025-07-15T12:18:49Z","type":"item","id":"Q1085185","labels":{"en":{"language":"en","value":"General factors of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3981220"}},"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":"Q1085185$B0B3E9C4-7795-4164-99ED-6585AE47F300","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"42063e371e412f19f684344f735475a3f3682560","datavalue":{"value":{"text":"General factors of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1085185$114EE783-D242-49DE-AD6B-13009658FC3F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"88338d0de242c5ade5cdee83de8deb6dcad0bf70","datavalue":{"value":"0607.05053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085185$97470B12-7D55-408D-96C6-34CF50DBCEEB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0c531ecdc33d83ae4d368dcaff026183ef3c10cd","datavalue":{"value":"10.1016/0095-8956(88)90068-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085185$1846EB1C-3893-4761-9070-B7BACBD1DBD7","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":"Q1085185$E841176A-686C-4FEE-A7FA-F9274201648F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1085185$3F04EF90-09D3-4B29-A530-35BE146A03A2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a57dcf11ca62bc490482bf3a960597180a3792af","datavalue":{"value":"Consider a graph \\(G=(N,E)\\) and, for each node \\(i\\in N\\), let \\(B_ i\\) be a subset of \\(\\{0,1,...,d_ G(i)\\}\\) where \\(d_ G(i)\\) denotes the degree of node i in G. The general factor problem asks whether there exists a subgraph of G, say \\(H=(N,F)\\) where \\(F\\subseteq E\\), such that \\(d_ H(i)\\in B_ i\\) for every \\(i\\in N\\). This problem is NP-complete. A set \\(B_ i\\) is said to have a gap of length \\(p\\geq 1\\) if there exists an integer \\(k\\in B_ i\\) such that \\(k+1,...,k+p\\not\\in B_ i\\) and \\(k+p+1\\in B_ i\\). Lov\u00e1sz conjectured that the general factor problem can be solved in polynomial time when, in each \\(B_ i\\), all the gaps (if any) have length one. We prove this conjecture. In cubic graphs, the result is obtained via a reduction to the edge-and-triangle partitioning problem. In general graphs, the proof uses an augmenting path theorem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085185$F4583534-1A6B-4AAA-8143-C07055CED1D1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085185$002BA355-B08F-4FDF-92D2-1C08C2A9EE9C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3ec5dfdc7cff6a942294be784d98b7fc566c67e6","datavalue":{"value":"3981220","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085185$9D2FEEDF-D729-4AC4-84EE-3733B97A96F3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcc771f9c4cbb132a4fb9368403bb895cba44b70","datavalue":{"value":"matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085185$4D0A6C7C-83A8-47C0-A1B6-845124022DE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb28958ba38d5ac199c8c66c546d35defaaa59a0","datavalue":{"value":"general factor problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085185$77EF083B-DEA7-4793-A09E-9B91B6362BDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085185$2EC7E0E3-0CA3-4CDC-B2BF-493221A75C2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3064a071ed381ab2df3a4f246fe1241b04efeffe","datavalue":{"value":"gap of length","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085185$DB63AB18-BE00-4BD0-8BE2-F69811A97270","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3e2c5cdbb9bf737c4fa7ac78971f831677d8a1d","datavalue":{"value":"graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085185$CF1755F3-6369-43AD-877C-3838217F4E57","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"feb07495fa8de76912d587852b3aa20404b344f1","datavalue":{"value":{"entity-type":"item","numeric-id":163019,"id":"Q163019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085185$7F8FFF7F-AF76-4395-BEB3-4D3CCB6D17B6","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":"Q1085185$1D9D0795-5CFB-48FD-A88E-2889A0A608EF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"44239d05dbbc0cf76322b523907f545fea20ef57","datavalue":{"value":"https://doi.org/10.1016/0095-8956(88)90068-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1085185$2602A3F3-ABBC-4C4A-A90A-22BD82D925E1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fec806416bad54ad25c1a1cad8c3cd77a63d3bc2","datavalue":{"value":"W2054076729","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085185$A783D808-4122-466D-B427-CCF80B138E9A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3de7edad0b76fa41f3d5b9d1b0f37d5e44dc7a8a","datavalue":{"value":{"entity-type":"item","numeric-id":1166429,"id":"Q1166429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085185$EA2DEBD7-44A4-4ECD-ADD1-EA7876AA9CFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6db8bab2b6b4db51137d491f1da9280274410f7a","datavalue":{"value":{"entity-type":"item","numeric-id":3745303,"id":"Q3745303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085185$1AA3A771-0D17-4684-8A99-D9A90BC9FD12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"271059027ec9c0e0491187496cb25dd92d2df81b","datavalue":{"value":{"entity-type":"item","numeric-id":5675543,"id":"Q5675543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085185$2762E664-06D7-4D2A-828D-F0A7F6B1F6E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4b70304ff30a1256f46103099164d048b244266","datavalue":{"value":{"entity-type":"item","numeric-id":4766817,"id":"Q4766817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085185$73A220CE-D3C2-436F-A6C4-73BF164C6BBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c00bceff6f60fb60810dddb1bd6a2b2ff394b899","datavalue":{"value":{"entity-type":"item","numeric-id":5595084,"id":"Q5595084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085185$AB795C43-6009-4FC3-A4EE-759755987BC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9a3ada332d9b1d8bf5360191802e9e5d56978f0","datavalue":{"value":{"entity-type":"item","numeric-id":5659592,"id":"Q5659592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085185$9B524F04-1A20-417C-9E8B-773725265612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4969d6a80ed53fd7ef27bdf261cf43fcb201bac","datavalue":{"value":{"entity-type":"item","numeric-id":1393414,"id":"Q1393414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085185$4CB514AB-A9D0-40F2-8D08-21E9F3DC3095","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085185$4AA8B89E-65D3-48FA-BA1D-053BA1D72B33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3fb5f043baeb68cce6e45f22256fe3a039c78a8","datavalue":{"value":{"entity-type":"item","numeric-id":5816402,"id":"Q5816402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085185$422D53DD-25B9-411A-87C3-70627D5C0F67","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":"Q1085185$981BC4F5-339C-4E41-A36A-5592AEC56C3E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d07879475dd8453b77a7479121cafed4d683f5f","datavalue":{"value":{"entity-type":"item","numeric-id":2767377,"id":"Q2767377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b64cf5ea9d9b10fce1335afc4b6323b309a28ae2","datavalue":{"value":{"amount":"+0.93675065","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1085185$619C6FD1-791F-47F1-842C-6F816A8E0A5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cfa0870bb52806057ae68f961be95af14544588","datavalue":{"value":{"entity-type":"item","numeric-id":4877004,"id":"Q4877004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d115cd81ead06c92d74a4af07655bfc24e7f273","datavalue":{"value":{"amount":"+0.9298197","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1085185$ADFB0248-6F12-4748-8F63-BCD64E4FA044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6db77fcdff5db0d1df272b9de5ea9152c29ecc8","datavalue":{"value":{"entity-type":"item","numeric-id":5492666,"id":"Q5492666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81ab1655b85678af18b066586a103c89d0f7cbbf","datavalue":{"value":{"amount":"+0.9241187","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1085185$2B1879F8-69E9-4E33-B059-1C1BFF9FE26B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ee0238d43c606731346f2bc062608a97c9a5d45","datavalue":{"value":{"entity-type":"item","numeric-id":4498983,"id":"Q4498983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e4d0c654806dd52bf48909e357867a6db6a1806","datavalue":{"value":{"amount":"+0.91827154","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1085185$BFE6C307-0C03-4B65-B6DF-F2C6184402EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24449d8792f4c2f624df00457c2fff7eb508f55e","datavalue":{"value":{"entity-type":"item","numeric-id":3682514,"id":"Q3682514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04165c2b72f71090f284a7613149b25505e988ab","datavalue":{"value":{"amount":"+0.9171477","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1085185$A1158B55-FF7D-4DE2-B778-E4C5F2685557","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d50410c3e1e7338ffaea98a972a7e42225a10fd6","datavalue":{"value":{"entity-type":"item","numeric-id":1074601,"id":"Q1074601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04165c2b72f71090f284a7613149b25505e988ab","datavalue":{"value":{"amount":"+0.9171477","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1085185$0A95910C-B825-4C35-AC60-1DC34818C1A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f39af840de6a20e84856153b3b59aab6cd3e799a","datavalue":{"value":{"entity-type":"item","numeric-id":3337508,"id":"Q3337508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50d0c06713a6efd9f4434ec889ede469f3da2461","datavalue":{"value":{"amount":"+0.91345274","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1085185$0ADA74EE-3BFC-4941-BC1A-F8D1CDDF0C3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"680cf37708bd823e33f76602b4e33dbfd5c2ee46","datavalue":{"value":{"entity-type":"item","numeric-id":3745874,"id":"Q3745874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b1adc60102191c4d17e9c8e3b146ba0dc0856bf","datavalue":{"value":{"amount":"+0.91325897","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1085185$A257B63E-E7B8-4A30-BF91-D54C8E468BA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b140c7c681d66a54fc357b7d4d7629b14e7798c","datavalue":{"value":{"entity-type":"item","numeric-id":5408597,"id":"Q5408597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abe1959decaf667c2a2c4ea42d9589a0fea39c93","datavalue":{"value":{"amount":"+0.9121045","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1085185$A5E47838-DFA8-4AD4-86C5-5314415E94B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"562ba4997721529747aefbef79d6a36297a4ced7","datavalue":{"value":{"entity-type":"item","numeric-id":5387016,"id":"Q5387016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7c8108034f45f0d29aef494e6306e6a8168eca7","datavalue":{"value":{"amount":"+0.9077208","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1085185$8BB89ED5-BEEA-4096-B07A-44D8ACA54861","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1085185","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1085185"}}}}}