{"entities":{"Q1400964":{"pageid":1411704,"ns":120,"title":"Item:Q1400964","lastrevid":67354950,"modified":"2026-04-12T17:03:53Z","type":"item","id":"Q1400964","labels":{"en":{"language":"en","value":"Bounded size components -- partitions and transversals."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1965034"}},"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":"Q1400964$D95C9C90-2F00-47FF-A293-267DFBC6EAB1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"480e336265082ecb850fb5950e47dc17eb7442a5","datavalue":{"value":{"text":"Bounded size components -- partitions and transversals.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1400964$40D3B287-55C0-4C50-AA46-E93495C663D7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"82c97a4bd099bdad8bb50990436b6b27cbe1c293","datavalue":{"value":"1033.05083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1400964$7D5A2C0A-91F8-4E93-AFC8-A52A25D61889","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"884ae59d4fb1450a6b75c4c47f03e67c8b8ac858","datavalue":{"value":"10.1016/S0095-8956(03)00031-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1400964$21B2904E-B149-45CA-9691-8BA2403B1262","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7e2180975cc0441c74630baede04a356d62197c","datavalue":{"value":{"entity-type":"item","numeric-id":290808,"id":"Q290808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$6C8742AF-1055-4E26-B53C-78401CD944C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bfb4a17abdcf37f7572da8c995af52b66fc8d692","datavalue":{"value":{"entity-type":"item","numeric-id":168595,"id":"Q168595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$B207D704-1063-40F6-99B2-694610DEEEBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef9f22506a0bcbf1151d6523fea2bf6c3ee4e900","datavalue":{"value":{"entity-type":"item","numeric-id":353398,"id":"Q353398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$041B8CAF-4998-40C3-816B-E11159F02B08","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":"Q1400964$8045AA0B-177F-497B-BB09-93CE31A43363","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7c559667253af6b857a12c847a2fbcea5328ae19","datavalue":{"value":{"time":"+2003-08-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1400964$8707159B-D22F-4628-9EE2-9848C3E8BB69","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f902d841ae1a82fb245e2791d32d20175ae7b1d6","datavalue":{"value":"The authors prove that there is an absolute constant \\(C\\) such that the vertex set of every graph with maximum degree \\(5\\) can be partitioned into \\(2\\) parts such that the subgraph induced by each part does not have a component of size larger than \\(C\\). This way they solve a problem posed by Alon at al. Moreover, they show that the vertex set of every graph with maximum degree 4 can be partitioned into 2 parts such that the subgraph induced by each part does not have a component of size larger than \\(6\\). The next result says that it is possible to partition the vertex set of a graph with maximum degree at most 8 into 3 parts such that each part induces components of size at most an absolute constant \\(C\\). Results concerning partitions of graphs of a given maximum degree into \\(k\\) parts (\\(k>2\\)) are given too. Finally, the authors prove that if the vertex set of a graph \\(G\\) is partitioned into subsets of size at least \\(\\Delta +\\lfloor\\Delta / r\\rfloor\\) (where \\(\\Delta\\) is the maximum degree of \\(G\\)) then there exists a transversal for this partition that induces in \\(G\\) a subgraph with all components bounded in size by \\(r\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1400964$2AD4901D-CE6D-4B3D-A600-50F46F585FAD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2e24c05a8d3e4c23a551354bc6bd226b3d93e379","datavalue":{"value":{"entity-type":"item","numeric-id":298334,"id":"Q298334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$2FD814A1-C07D-4510-9F72-7A47696EE321","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1400964$D708FAF3-31B7-4CE4-A82C-34B01D3A76F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1400964$E61EFBFE-8A90-4DFD-BD62-62025F2F7E75","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d53d7ec1b3057b851a922ee816a1353f604cd511","datavalue":{"value":"1965034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1400964$88D1C48D-12B6-4AE1-94EC-87D65348F12A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09f63191468a51acb7e8ab5f4b9973fde094ec55","datavalue":{"value":"partition of vertex set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1400964$18E36315-F317-47D3-BD37-2D9672A9C836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf77f5770ff7e72f9f67548a358649cff8331a86","datavalue":{"value":"bounded size components","type":"string"},"datatype":"string"},"type":"statement","id":"Q1400964$5C1D970A-6A72-4532-926F-E4A103C19A25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fde7375354c9bf3677df2f131632a17ad70cf552","datavalue":{"value":"transveral","type":"string"},"datatype":"string"},"type":"statement","id":"Q1400964$C92EBAA7-73AB-45E4-9B64-C957A5312AC1","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":"Q1400964$C5BBBA04-982E-410A-ADF0-516388C67E5C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"591f6b8435a2e5b2b7d96b7a89ea5720be67ba98","datavalue":{"value":{"entity-type":"item","numeric-id":3907606,"id":"Q3907606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$05866903-18AF-4E5D-B5C1-DE11D60A535F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19aafb0d768a31243436a77bcbbe4167aa96c8c1","datavalue":{"value":{"entity-type":"item","numeric-id":4222072,"id":"Q4222072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$2E923829-CCA4-43BE-8019-E72B5A696D01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb4cd0043520378950644a1497cfc0310df533c0","datavalue":{"value":{"entity-type":"item","numeric-id":1405114,"id":"Q1405114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$BA55D768-E0E8-4D5D-8839-1668AC9BA24F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4799e5a32c687eea79d573479ff8c58240f3cb62","datavalue":{"value":{"entity-type":"item","numeric-id":4004078,"id":"Q4004078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$B2FA8A9F-DC73-43CD-87E1-5245D398CBE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38b451f059814158c911074afe693b201879c742","datavalue":{"value":{"entity-type":"item","numeric-id":761470,"id":"Q761470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$D3420951-3261-44BD-A6BC-1AA44A402099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"835719973f233409024ef3cbbd019c8eb10bd440","datavalue":{"value":{"entity-type":"item","numeric-id":1217812,"id":"Q1217812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$EBF1F680-BDF9-4A1D-BDBD-019D6CA2080B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a59347f73363b99fbc0fc253b8806d6552a0453","datavalue":{"value":{"entity-type":"item","numeric-id":4074927,"id":"Q4074927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$B5C4FD4F-C333-4D91-954B-87A1AB9F2E94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c99b316fd9ad08a3bd82e78023403d5ad975501d","datavalue":{"value":{"entity-type":"item","numeric-id":2757076,"id":"Q2757076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$51C2A65F-6E19-425D-AF6E-9421890B303A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e17b27dea6e8ef7f0fed8cf092cb4dc3f3602e9","datavalue":{"value":{"entity-type":"item","numeric-id":1356680,"id":"Q1356680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$B789FF2F-6291-43CB-A22B-107CE0F4B760","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74074974e02935f8f5ecb942cc6fe70f08b746ea","datavalue":{"value":{"entity-type":"item","numeric-id":5530470,"id":"Q5530470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$64B089E7-8536-41B9-B835-83719779F53C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d121cdeb1c638d1e652d84e6b13b6dcfaac9d2b3","datavalue":{"value":{"entity-type":"item","numeric-id":1306426,"id":"Q1306426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$51117AEC-DB1B-459E-8FB1-3F6C6C0DCE0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"487686cc416dc331230665649ac2323b366ee885","datavalue":{"value":{"entity-type":"item","numeric-id":1377695,"id":"Q1377695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1400964$0DE26C8D-DD17-4EC9-BAC8-23920773CBBE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"161de1abe2375015a9f0298d625bb427292f0589","datavalue":{"value":"https://doi.org/10.1016/s0095-8956(03)00031-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1400964$B722E91F-D316-416D-8796-3880A02C6209","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f29699ceeb3e3d345e00493746c7bbfbd4e862f2","datavalue":{"value":"W1986861105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1400964$64A484BF-484C-469E-8CB4-C8B2CA785D21","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da77590fa34a491f9e86a5938a542e9760ac0690","datavalue":{"value":{"entity-type":"item","numeric-id":1405114,"id":"Q1405114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b2ad417a00478cc418b7280318c9aeb03cbaaec","datavalue":{"value":{"amount":"+0.8640575408935547","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":"Q1400964$34A633CA-6283-444F-9476-B13EDF820079","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee2523259fc945b67b78d33231b2c7b3443d27f0","datavalue":{"value":{"entity-type":"item","numeric-id":4987260,"id":"Q4987260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b2ad417a00478cc418b7280318c9aeb03cbaaec","datavalue":{"value":{"amount":"+0.8640575408935547","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":"Q1400964$9E64A085-F05D-49B5-AD39-41A087660974","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d18b1695657f3b7e32418162ce512ca9c70920ab","datavalue":{"value":{"entity-type":"item","numeric-id":855115,"id":"Q855115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90ae116554f1acc58e6f8b9ffdb9985bc4cdbba5","datavalue":{"value":{"amount":"+0.830113410949707","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":"Q1400964$2B314B8B-038B-43B4-8A21-83F51C8CF436","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22fb1a2c73bd9e36ebf9a9580532f7ca7c77c46b","datavalue":{"value":{"entity-type":"item","numeric-id":4474279,"id":"Q4474279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91ae12c83f698c92a384cb91facaae3adcc2a472","datavalue":{"value":{"amount":"+0.8068705201148987","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":"Q1400964$03ACE2B3-6AB7-4D22-9E2C-AA0D2BCD272F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"482926090b2156d64f2d52cd762809c70844443e","datavalue":{"value":{"entity-type":"item","numeric-id":2384801,"id":"Q2384801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd9d852d6485536e37f4b906e86714ddefe413a0","datavalue":{"value":{"amount":"+0.7965912818908691","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":"Q1400964$B249ED57-F752-46AB-B908-1893FA3BCE6B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounded size components -- partitions and transversals.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounded_size_components_--_partitions_and_transversals."}}}}}