{"entities":{"Q2848743":{"pageid":2859463,"ns":120,"title":"Item:Q2848743","lastrevid":58037181,"modified":"2026-04-03T13:33:09Z","type":"item","id":"Q2848743","labels":{"en":{"language":"en","value":"Covering cubic graphs with matchings of large size"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6212192"}},"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":"Q2848743$5BBC3EBA-07BC-4E12-9454-CF2741EFBFAC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b94a43780901bbf2c3d18551a4c705b5c76f56e4","datavalue":{"value":"1277.05135","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848743$28CA0342-EF8A-48B0-A4F8-2E64AB0E0D7D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"43e878d8f753446abefa1b1ceb0637b91afae47a","datavalue":{"value":{"time":"+2013-09-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2848743$CB4396EF-BB53-4665-B834-B6A1601A43CE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aac51b278202930788c54ceea7854fe2bf315755","datavalue":{"value":"https://arxiv.org/abs/1210.3930","type":"string"},"datatype":"url"},"type":"statement","id":"Q2848743$F701362A-23AD-4B27-A8DF-FD916E50BF25","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848743$17377F7E-0A25-48B9-9D74-C19A93EF01E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848743$AD41FC5D-315F-4842-8D35-3A67A0972DC0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"25844fdcf494f6ec068f2e729682b041660070d8","datavalue":{"value":"6212192","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848743$6D73DE3D-C5E7-4FDD-9F93-7741CC262C4F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8246134fea2daf7b9c9b0d32f534a3244997b2fb","datavalue":{"value":"\\([m]\\)-matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848743$778BB5DA-2735-4C88-BFE7-798E5F39C90E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8ad353b76423500cfde6793601e00e7df111dd5","datavalue":{"value":"excessive \\([m]\\)-index of a graph \\(G\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848743$A4EC6477-B5E6-47EB-95EC-D477815BAA9D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e3e5eb88cb46e6b4a80741b2023a7c7ec642ee6a","datavalue":{"value":{"entity-type":"item","numeric-id":663466,"id":"Q663466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848743$545EBB93-1C7F-4F84-99CF-7494D8398249","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"39c4163d00db19bed4405f38e5a94302027e100f","datavalue":{"value":{"entity-type":"item","numeric-id":322187,"id":"Q322187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848743$54EF847A-08BD-4271-90B7-5933C108FAA9","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":"Q2848743$2AF2FC93-61B8-4D95-A0D2-53EA04165D01","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2427fa71cfdd49590b0bb4f037424c935d946588","datavalue":{"value":{"entity-type":"item","numeric-id":2516508,"id":"Q2516508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"608fec1304c9aedbd226ba1f6145882536f59fe3","datavalue":{"value":{"amount":"+0.83251476","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848743$5C7D3513-AE68-4FF7-807F-66E746B75138","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7530a9f15cd5ec4d2b34b4dae423f94ef18fdc5f","datavalue":{"value":{"entity-type":"item","numeric-id":1880788,"id":"Q1880788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"784e33bcd895e263cc3d6fbfd895773903e40576","datavalue":{"value":{"amount":"+0.7934712","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848743$8F3E0AED-64ED-467B-AEB0-C2492E49E8FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a6398490b3b3f16a44535334396750a69752df1","datavalue":{"value":{"entity-type":"item","numeric-id":2306590,"id":"Q2306590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b3161d9e6f76a4e27f4b77d36024e7de59d9297","datavalue":{"value":{"amount":"+0.7899673","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848743$5FF7693F-1292-4020-9275-9C985FB00764","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e120457c5b2e8ea9fb3a1f8fac4475586e65da73","datavalue":{"value":{"entity-type":"item","numeric-id":281587,"id":"Q281587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5973f42df59b656bf52e3ad9d53c68224d72344f","datavalue":{"value":{"amount":"+0.7828356","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848743$7DE46345-118F-4286-9944-1288E3E153D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f6f62f36c1e82e1b3594d43212be8aac46ccdf1","datavalue":{"value":{"entity-type":"item","numeric-id":3752403,"id":"Q3752403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b05b13155fd872c5c7ab7f29d3e92753c2b838f","datavalue":{"value":{"amount":"+0.77577204","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848743$D7AFD6CA-15DC-40DA-9E8B-4DDA73422E5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4b3f83eb10a0873cbde327b0b897c83684d2676","datavalue":{"value":{"entity-type":"item","numeric-id":968438,"id":"Q968438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"158759eefecef41f6861840005fc6b03c2d6d6d6","datavalue":{"value":{"amount":"+0.7749348","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848743$DCF5D952-B98D-4A30-9982-8A6A49C4ED87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fcb559ffd30619756d361a1f0b7ea9df9cfe81c","datavalue":{"value":{"entity-type":"item","numeric-id":2448882,"id":"Q2448882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85d572d8ace78a2bdc4c458cd8a66b03656aa0b1","datavalue":{"value":{"amount":"+0.77074564","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848743$92DB60DE-9235-4AA2-889B-EB18150700CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0790f9e17cac7488d92761d7406aeb072221a52a","datavalue":{"value":{"entity-type":"item","numeric-id":5502080,"id":"Q5502080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f19f67e12d0ccc23c92bdd5c0909575446f0c24","datavalue":{"value":{"amount":"+0.76736057","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848743$F55110AC-C43F-452D-819D-4B2C263D4178","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eca7d21a00b1ef84546a256b706e6148b4de7568","datavalue":{"value":{"entity-type":"item","numeric-id":960925,"id":"Q960925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad46f1f8a175011534593e1bf76229ea579fb504","datavalue":{"value":{"amount":"+0.7658692","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2848743$8C11086F-1A83-4850-8DF7-9557EB7A43E0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b1e41367439940e7f472de7913a44ce192455a35","datavalue":{"value":{"text":"Covering cubic graphs with matchings of large size","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2848743$31DF775D-6CB5-476D-9ED8-2F915294D0E0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4475e942e511a8e1762a91638eb522e6040025ba","datavalue":{"value":{"entity-type":"item","numeric-id":6562416,"id":"Q6562416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848743$F99C35D6-8D4D-448F-93F5-44B4C70A74AA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d713bb9634a2c7522a52d2a9a18f1486d0c63e31","datavalue":{"value":"An \\([m]\\)-matching is a matching with \\(m\\) pairs. The excessive \\([m]\\)-index of a graph \\(G\\), denoted by \\(\\chi_{[m]}^\\prime(G)\\) (cf. [\\textit{D. Cariolaro} and \\textit{H.-L. Fu}, Discrete Math. 310, No. 2, 276--287 (2010; Zbl 1243.05192)]) is the minimum number of \\([m]\\)-matchings needed to cover the edges of \\(G\\).NEWLINENEWLINE Proposition 1. Let \\(G\\) be a cubic graph of order \\(2n\\). If \\(m<\\frac{3n}4\\), then \\(\\chi_{[m]}^\\prime(G)=\\left\\lceil\\frac{3n}m\\right\\rceil\\).NEWLINENEWLINE Proposition 2. For every positive integer \\(m\\) there exists a positive integer \\(n\\) and a cubic graph \\(G\\) of order \\(2n\\) such that \\(\\chi_{[n-1]}^\\prime(G)\\geq m\\).NEWLINENEWLINE Proposition 3. Let \\(G\\) be a 3-edge-colourable cubic graph of order \\(2n\\geq8\\). Then \\(\\chi_{[n-1]}^\\prime(G)=4.\\) The second author has proved [J. Graph Theory 68, No. 2, 125--128 (2011; Zbl 1230.05238)] that a conjecture of Berge and Fulkerson [\\textit{D. R. Fulkerson}, Math. Program. 1, 168--194 (1971; Zbl 0254.90054)] can be expressed as Conjecture 2. If \\(G\\) is a 3-graph of order \\(2n\\), then \\(\\chi_{[n]}^\\prime(G)\\leq5\\).NEWLINENEWLINE Proposition 4. The Berge-Fulkerson conjecture implies that \\(\\chi_{[n-1]}^\\prime(G)\\leq5\\) for each cubic graph \\(G\\) of order exceeding 4.NEWLINENEWLINE A snark is a cyclically 4-connected non-3-edge-colourable cubic graph of girth at least 5.NEWLINENEWLINE Proposition 5. Let \\(G\\) be a snark of order \\(2n\\leq32\\). Then \\(\\chi_{[n-1]}^\\prime(G)=4\\).NEWLINENEWLINE The oddness of a cubic graph is the minimum number of odd circuits in a 2-factor.NEWLINENEWLINE Proposition 6. Let \\(G\\) be a cubic graph of order \\(2n\\) and oddness 2. Then \\(\\chi_{[n-1]}^\\prime(G)=4\\).NEWLINENEWLINE Proposition 7. Let \\(G\\) be a cyclically 4-connected cubic graph of order \\(2n\\) and oddness 4. Then \\(\\chi_{[n-1]}^\\prime(G)=4\\).NEWLINENEWLINE A cubic graph \\(G\\) is \\(3^*\\)-connected if it has vertices \\(a,b\\) which are the end-vertices of three openly disjoint paths \\(Q_1\\), \\(Q_2\\), \\(Q_3\\) such that \\(V(G)=\\bigcup\\limits^3_{i=1}V(Q_i)\\) [\\textit{M. Albert} et al., Australas. J. Comb. 24, 193--207 (2001; Zbl 0982.05062)].NEWLINENEWLINE Proposition 8. Let \\(G\\) be a \\(3^*\\)-connected cubic graph of order \\(2n\\), with \\(n\\geq4\\). Then \\(\\chi_{n-1}^\\prime(G)=4\\).NEWLINENEWLINE Proposition 9. Let \\(G\\) be a cubic graph of order \\(2n\\geq8\\) and longest circuit at least \\(2n-2\\). Then \\(\\chi_{[n-1]}^\\prime(G)=4\\).NEWLINENEWLINE (Caveat lector! Some apparent misprints have been corrected in the preceding list of propositions.)","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848743$B6B9AB6B-F0CA-4C72-9014-37A32546C0CA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848743$3084A1F4-92A9-400E-BB10-DC3B965D296A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2848743","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2848743"}}}}}