{"entities":{"Q286756":{"pageid":288523,"ns":120,"title":"Item:Q286756","lastrevid":60662190,"modified":"2026-04-10T18:21:52Z","type":"item","id":"Q286756","labels":{"en":{"language":"en","value":"Toward \u017bak's conjecture on graph packing"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6585223"}},"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":"Q286756$CFF27390-82CF-46C3-927D-9FCFAD9F102E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"550591428b0d3e3aff0a1c39e9b7372031838487","datavalue":{"value":{"text":"Toward \u017bak's conjecture on graph packing","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q286756$AA2214FF-2E24-45D0-94B6-0B9423A4610B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aecd80c73c0d3644a681b29fcd39778ec0f9b4a9","datavalue":{"value":"1350.05137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286756$ED3D6C18-77D1-4CE7-A477-4E6E7A1A2A55","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a112fcddf40de3e0f26627c12549da4365ccc05","datavalue":{"value":{"entity-type":"item","numeric-id":214987,"id":"Q214987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q286756$5D97B610-6BF5-45CF-8F9B-34C5B7487914","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8fa7d3948e2aaad237a03c07a1632e4de9bb0730","datavalue":{"value":{"entity-type":"item","numeric-id":284762,"id":"Q284762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q286756$C15366A8-3E71-46E1-8E9F-3D2DD6FE6AC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"63e99339289fc2e7c23df3bd959eace7c33ce1b0","datavalue":{"value":{"entity-type":"item","numeric-id":276200,"id":"Q276200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q286756$C3E5E738-E341-48B9-BA45-667EDE523962","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dfaf7e39ce7242df810dc90e03bf20c559cdc99f","datavalue":{"value":{"entity-type":"item","numeric-id":1165243,"id":"Q1165243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q286756$72ABA8E2-1680-43A1-BFBB-2A7F8EF7D0C6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6b8b858ece76e2bb88c236d487f13fce9f1e9789","datavalue":{"value":{"entity-type":"item","numeric-id":247199,"id":"Q247199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q286756$60A6B251-6C2D-42A1-9874-66EE7C57220D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b3df5911fe2651c5b316b1c434feff8234703d15","datavalue":{"value":{"time":"+2016-05-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q286756$16AADCB9-DF64-46E1-AE1E-CB884B604000","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f4a8ed28600ea8b79676f1a202500988c31a91d7","datavalue":{"value":"https://arxiv.org/abs/1508.03672","type":"string"},"datatype":"url"},"type":"statement","id":"Q286756$FCECD7B2-D1CC-46D9-9E47-559188C723DE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286756$32C6F6FF-DCB4-4648-8A64-FC01F0169640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286756$3416DCBB-2E96-410E-8CB5-A65293266FDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286756$8337FE77-EC4B-4293-B92B-BA66D7A2DDB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286756$43675F69-4810-4C52-910E-1E53450F65B6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8f3d18ee53aca2d992a48185c548cd19379f7854","datavalue":{"value":"6585223","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286756$628FE5EA-BFC5-469B-B38B-F36EAE0DA20F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c673080127e1d2f44f24cd80d57f7846b39549a8","datavalue":{"value":"graph packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q286756$3C2AC1E2-6073-44B3-B991-745C246A5662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13196c9c8a3f396e97e9426bc7763f437026aa4b","datavalue":{"value":"maximum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q286756$82BF0160-C1A8-4634-84A2-1D9F6C10D823","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"644abe564421748f2e700b98d603edb287874aab","datavalue":{"value":"edge sum","type":"string"},"datatype":"string"},"type":"statement","id":"Q286756$5CB3D168-D1E7-40B7-A962-7A3E86089C77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5f6aefdf1ffec3bc08d67d0b64a04330c0d9134","datavalue":{"value":"list coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q286756$03A188F7-6E29-4257-A38B-F3AAAD5EAF99","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":"Q286756$D8007B79-B9FD-443F-95BA-1729FB7173D0","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"2902fea6a2c4a4b3c306efcb516fdfa084cea249","datavalue":{"value":"Q123015876","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286756$85387E5E-6923-431D-9989-D8576B513BF3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1812fbe15f55d804c6b7520e1c02f11b2928a40d","datavalue":{"value":"W2963857888","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286756$CFFDA59A-B986-4BA1-91B3-D23D5814A5E2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b438e2ef7c66243c7da1c72ec909157b7d6d459f","datavalue":{"value":"10.4310/JOC.2016.V7.N2.A6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286756$6ACA98B3-F40B-4F82-BA49-A63B3C7C5F9F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3662d8ca17b107bf4e5e02717da209417e6e2cb0","datavalue":{"value":{"entity-type":"item","numeric-id":5704386,"id":"Q5704386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f1a8ca39fcf543fbc7360c2ce51503bcba592e0","datavalue":{"value":{"amount":"+0.9309828","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":"Q286756$0F5D7D9C-3447-4326-A640-C6CDBEF5C981","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3332f73fbee4642eb83306bb4ddb5ce7e89cb53","datavalue":{"value":{"entity-type":"item","numeric-id":987545,"id":"Q987545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f07f0719d086cf17c524c0d61c78c2ef6425ca7","datavalue":{"value":{"amount":"+0.9206554","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":"Q286756$99B910E2-AA0C-4D35-994B-EE5F891007EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67fc65f24f6ff236b620191541cc5a2332ea5dd0","datavalue":{"value":{"entity-type":"item","numeric-id":4614038,"id":"Q4614038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f58f41fa1dad9aa986f33c7a2fa8b16421dedb8","datavalue":{"value":{"amount":"+0.92019355","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":"Q286756$D2B94C5E-FC02-42C2-9FEB-6FC1799E850B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67c2e8c37aa89dfcbcc44b775b62a862fd0bb24c","datavalue":{"value":{"entity-type":"item","numeric-id":4690988,"id":"Q4690988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c67a08b708af68fa4aca799cdd6797a17b7a6a7e","datavalue":{"value":{"amount":"+0.9193518","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":"Q286756$6DB00A2E-1B9F-445C-BEDD-2E82318F6966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2291fd83ea6efae844e997eba946f1fd39e5bb9b","datavalue":{"value":{"entity-type":"item","numeric-id":4940073,"id":"Q4940073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44d35ea2a92e6e5ca61a74de5407ad23c10555a4","datavalue":{"value":{"amount":"+0.91792274","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":"Q286756$F6C18A0D-53DA-480C-A78D-72CD7A171E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0d5c4cfb872aa1eccba363cdc5e15a820eeb428","datavalue":{"value":{"entity-type":"item","numeric-id":1825885,"id":"Q1825885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eec0de502fa6347241b834fc92aac233fec533ea","datavalue":{"value":{"amount":"+0.9152394","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":"Q286756$D5AF5764-96E2-457A-B043-6FDD09AEC02F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce6a759fcf0ddadead7d5a47b64d03a33c3fbdac","datavalue":{"value":{"entity-type":"item","numeric-id":4340018,"id":"Q4340018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7388eafdf7d30af6d96896a61eb0b9ae520478de","datavalue":{"value":{"amount":"+0.9127294","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":"Q286756$7A058FAD-BFDC-4149-B676-817545D23A5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec4e00d017a4aa1a9b1d03d7c55a4dce548d6eac","datavalue":{"value":{"entity-type":"item","numeric-id":2715943,"id":"Q2715943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca275addd7d0ca144070ea9d2f6228ffeb769f34","datavalue":{"value":{"amount":"+0.9120822","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":"Q286756$3D0BF60F-10E0-43C3-AA8F-4C7191030AD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a90a9b5e30e2ad1e887c7d18a630b67a3dda18c","datavalue":{"value":{"entity-type":"item","numeric-id":1584285,"id":"Q1584285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86bb5d106ed93e56e98bbff697a962aac400df02","datavalue":{"value":{"amount":"+0.9087947","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":"Q286756$13B0814A-F026-4CC4-BB88-BCC8ADACA6D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"375e748f2d24c9e41e14eb712708c10597f753cf","datavalue":{"value":{"entity-type":"item","numeric-id":2816101,"id":"Q2816101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"979f0b4dbb74ed339e7e503810c94d347bbcdd97","datavalue":{"value":{"amount":"+0.90827197","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":"Q286756$A34D081A-FFB4-4D8C-9C4D-10F458D6468A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d13529ef9e2e16f9f26278b45b7f8956e3bb4343","datavalue":{"value":"The paper studies the problem of graph packing. Two graphs \\(G_1\\) and \\(G_2\\) with the same order \\(n\\) are said to pack if there is an edge-disjoint placement of them onto the same set of \\(n\\) vertices. Research on graph packing began in the below two papers, both published in 1978. In [J. Comb. Theory, Ser. B 25, 295--302 (1978; Zbl 0417.05037)], \\textit{N. Sauer} and \\textit{J. Spencer} proved that if \\(|E(G_1)|+|E(G_2)|<\\frac{3}{2}n-2\\), then \\(G_1\\) and \\(G_2\\) pack. \\textit{B. Bollob\u00e1s} and \\textit{S. E. Eldridge} [J. Comb. Theory, Ser. B 25, 105--124 (1978; Zbl 0387.05020)] obtained a stronger result that if the maximum degree of \\(G_1\\) and \\(G_2\\), \\(\\Delta(G_1),\\Delta(G_2)\\leq n-2\\), and if \\(|E(G_1)|+|E(G_2)|<2n-3\\), then \\(G_1\\) and \\(G_2\\) pack, with some exception.NEWLINENEWLINE\\textit{A. \u017bak} [SIAM J. Discrete Math. 28, No. 4, 1686--1698 (2014; Zbl 1314.05169)] combined the conditions on the number of edges and maximum degrees together, and obtained a stronger result for large graphs. Let \\(G_1\\) and \\(G_2\\) be two graphs of order \\(n\\geq 10^{10}\\). If \\(|E(G_1)|+|E(G_2)|+\\max\\{\\Delta(G_1),\\Delta(G_2)\\}<\\frac{5}{2}n-2\\), then \\(G_1\\) and \\(G_2\\) pack. Furthermore, \u017bak showed that the bound can be improved if the star on \\(n\\) vertices is forbidden. Let \\(G_1\\) and \\(G_2\\) be two graphs on \\(n\\) vertices with \\(\\Delta(G_1),\\Delta(G_2)\\leq n-2\\). If \\(|E(G_1)|+|E(G_2)|+\\max\\{\\Delta(G_1), \\Delta(G_2)\\}<3n-96n^{3/4}-65\\), then \\(G_1\\) and \\(G_2\\) pack. It is conjectured that the bound on the right side can be improved to \\(3n-7\\). NEWLINENEWLINENEWLINE In the present paper, the authors verify that \u017bak's conjecture holds up to the choice of the additive constant. Namely, Let \\(C=11(195^2)=418275\\). Let \\(G_1\\) and \\(G_2\\) be two graphs on \\(n\\) vertices with \\(\\Delta(G_1),\\Delta(G_2)\\leq n-2\\). If \\(|E(G_1)|+|E(G_2)|+\\max\\{\\Delta(G_1),\\Delta(G_2)\\}<3n-C\\), then \\(G_1\\) and \\(G_2\\) pack.NEWLINENEWLINENEWLINEThe proof of the theorem uses the concept of list packing. A graph triple \\(\\mathcal G=(G_1,G_2,G_3)\\) consists of two disjoint graphs \\(G_1=(V_1,E_1)\\) and \\(G_2=(V_2,E_2)\\) on \\(n\\) vertices, and a bipartite graph \\(G_3=(V_1\\cup V_2, E_3)\\) with partite sets \\(V_1\\) and \\(V_2\\). A list packing of \\(\\mathcal G\\) is a packing of \\(G_1\\) and \\(G_2\\) such that \\(uf(u)\\notin E_3\\) for any \\(u\\in V_1\\). What the authors prove is the list version of the main theorem. Let \\(C=11(195^2)=418275\\). Let \\(n\\geq 2\\) and \\(\\mathcal G=(G_1,G_2,G_3)\\) be a graph triple with \\(|V_1|=|V_2|=n\\), \\(\\Delta(G_1), \\Delta(G_2) \\leq n-2\\) and \\(\\Delta(G_3) \\leq n-1\\). If \\(|E_1|+|E_2|+|E_3|+\\max\\{\\Delta(G_1), \\Delta(G_2)\\}+\\Delta(G_3)<3n-C\\), then \\(\\mathcal G\\) pack.","type":"string"},"datatype":"string"},"type":"statement","id":"Q286756$C07D9A4D-1073-4611-A346-BD04792EFFD9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Toward \u017bak's conjecture on graph packing","badges":[]}}}}}