{"entities":{"Q987554":{"pageid":989402,"ns":120,"title":"Item:Q987554","lastrevid":42803587,"modified":"2025-07-11T15:40:49Z","type":"item","id":"Q987554","labels":{"en":{"language":"en","value":"Highly parity linked graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5770359"}},"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":"Q987554$EA6D1074-3C0E-4384-9683-937138FB19A5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cb553d72dce4ee9be0b22d2289dd7c7129647699","datavalue":{"value":{"text":"Highly parity linked graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q987554$80EA7D3E-2980-495F-B660-09102B0133A8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d7db250b25b0b671dba07b117ca50f7abe1ca2a6","datavalue":{"value":"1212.05143","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q987554$56595988-68D3-46C8-9B04-BF348B1D9E69","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q987554$706141CC-EFF8-40FC-978A-AD87F26D631B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"829d55f1ec544e7d684ffd95ef09a9fd350e7c82","datavalue":{"value":{"time":"+2010-08-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q987554$B62A0383-754C-41E9-9EEC-1FEE2E07F201","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"97fb5ba79dba8659e419bba5fbe5cdc0a67d19d8","datavalue":{"value":"The subject of the paper originates on the Erd\u0151s-P\u00f3sa property of graphs [\\textit{P. Erd\u0151s} and \\textit{L. P\u00f3sa}, Publ. Math. 9, 3--12 (1962; Zbl 0133.16701)]. A family \\(\\mathcal F\\) of graphs has this this property if for every \\(k \\in N\\) there is an integer \\(f(k,\\mathcal{F})\\) such that any graph \\(G\\) is either contains \\(k\\) vertex disjoint graphs from \\(\\mathcal F\\), or there is an \\(X \\subset V(G)\\) such that \\(G - X\\) contains none. They showed the family of cycles has the Erd\u0151s-P\u00f3sa property.   \\textit{C. Thomassen} [Combinatorica 21, No. 2, 321--333 (2001; Zbl 0989.05062)] showed that while in general the family of odd cycles does not have the Erd\u0151s-P\u00f3sa property, there is a function \\(f\\) such that if \\(G\\) is \\(f(k)\\)-connected then either \\(G\\) contains \\(k\\) disjoint odd cycles or \\(G\\) becomes bipartite after deleting an appropriate set \\(X \\subset V(G)\\) of size \\(2k-2\\).      The disjoint odd cycles are in close relation with the following notion. A graph \\(G\\) is \\(k\\)-linked if it has at least \\(2k\\) vertices, and for any \\(2k\\) vertices \\(x_1, \\dots, x_k\\), \\(y_1, \\dots, y_k\\) there are \\(k\\) pairwise disjoint paths \\(P_1, \\dots, P_k\\) such that \\(P_i\\) connects \\(x_i\\) and \\(y_i\\) for all \\(i=1, \\dots, k\\). \\textit{H. A. Jung} [Math. Ann. 187, 95--103 (1970; Zbl 0184.27601)] and \\textit{D. G. Larman} and \\textit{P. Mani} [Proc. Lond. Math. Soc., III. Ser. 20, 144--160 (1970; Zbl 0201.56801)] proved the existence of an \\(f(k)\\) such that every \\(f(k)\\)-connected graph is \\(k\\)-linked. (Note that the paper of Larman and Mani is incorrectly dated in this paper.) For that case \\textit{R. Thomas} and \\textit{P. Wollan} [Eur. J. Comb. 26, No. 3-4, 309-324 (2005; Zbl 1056.05091)] had the best result as every \\(10k\\)-connected graph is \\(k\\)-linked.  \\(G\\) is parity-\\(k\\)-linked if the parity of each \\(P_i\\) can be described. In the above mentioned paper Thomassen generalized his results as there exist functions \\(f(k)\\) and \\(g(k)\\) such that if a graph \\(G\\) is \\(f(k)\\)-connected, then it is either parity-\\(k\\)-linked or for some \\(X \\subset V(G)\\) the subgraph \\(G-X\\) is bipartite. In fact, the exact value is \\(g(k)=4k-3\\). The main theorem of this paper is the improvement of \\(f(k)\\), while Thomassen gave a double exponential upper bound, the authors show that \\(f(k)=50k\\) is enough. Their proof also improves the former results on odd cycles: A \\(24k\\)-connected graph \\(G\\) has either \\(k\\) disjoint cycles or a set \\(X \\subset V(G)\\) such that \\(| X| \\leq 2k-2\\) and \\(G-X\\) is bipartite.","type":"string"},"datatype":"string"},"type":"statement","id":"Q987554$0B32F344-23BE-484E-B626-703F75CAC43F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73456c3353ea197c90c73d5f0daaf3b9d502d311","datavalue":{"value":{"entity-type":"item","numeric-id":235726,"id":"Q235726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q987554$0F40EBCE-2524-4292-B1D0-4C078C1E857C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q987554$DAD6B6F9-0742-4642-9CB3-8D295C68D8BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49261cbbd2f3b64e072aca4630c2592536037a47","datavalue":{"value":"05C83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q987554$8DD9C2C2-CA5B-4BAF-81A9-7E5EA6589AE0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aba2fc02a267b6b8a6603c0973c2a08425cd1dcf","datavalue":{"value":"5770359","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q987554$42EEC095-285D-4E87-B34B-8EAC5898EB1C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1e873d9db9e15ad4edfa509d4c53375590d9fd0","datavalue":{"value":"Erd\u0151s-P\u00f3sa property","type":"string"},"datatype":"string"},"type":"statement","id":"Q987554$D9074DEA-2A39-4396-BA59-5A4741C37816","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01da712f43a2d6d48e56f18188439956cd875dba","datavalue":{"value":"parity k-linked","type":"string"},"datatype":"string"},"type":"statement","id":"Q987554$6280D8A8-9A04-4800-B953-ED3FA7BFD328","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f4e7bb5eb3d92423af4c11d1172a2aa89ed8c8c","datavalue":{"value":{"entity-type":"item","numeric-id":214979,"id":"Q214979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q987554$0F98E63D-9D84-4DF1-A6AB-3CB4F961D409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d98a938c7c496671aebe9d069bbd3d70f74a635a","datavalue":{"value":{"entity-type":"item","numeric-id":661944,"id":"Q661944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q987554$79835795-E679-4C9D-B004-E43799FE82BB","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":"Q987554$63DEEB51-6907-45C6-8593-3ED530E2AB8E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9256acafb424b12a940a27d91949ee5fbe81a875","datavalue":{"value":"https://doi.org/10.1007/s00493-009-2343-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q987554$108F0CB6-9BD6-4718-8158-ECC199A64A34","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1502fa6b3f4495b3a1751acb631fd7fb5ee8db01","datavalue":{"value":"W1812326786","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q987554$1493B5B5-2A95-4C47-BF4E-D13748611E41","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"49c1a3726e308971c94df1aefea7953d7ced2665","datavalue":{"value":"Q126580904","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q987554$3972095A-8E12-455D-B54B-47F307C83F18","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"73d0ba91be35a5164e9bd121419d5370aa4c66e3","datavalue":{"value":"10.1007/S00493-009-2343-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q987554$49892DF0-8F51-4045-B735-A9A4B16A3D12","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71f4f1dda46fff2f3af5f82f7ff3b3bc5c9bd610","datavalue":{"value":{"entity-type":"item","numeric-id":4978443,"id":"Q4978443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74eab0435336001f495f09854634ef2d203ea4f0","datavalue":{"value":{"amount":"+0.8530198","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":"Q987554$927AC5DE-1136-4570-B0F7-4C4382868AEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8f12696b39e0a574dee83865661d5443193f262","datavalue":{"value":{"entity-type":"item","numeric-id":2827821,"id":"Q2827821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b0771ef2e3b628da6c6deddec15b156211da182","datavalue":{"value":{"amount":"+0.8502735","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":"Q987554$720A024B-F44A-478F-9A38-242CC72FC97C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"892faf334f1e153569b89bf8a4518f4ccf57651c","datavalue":{"value":{"entity-type":"item","numeric-id":402593,"id":"Q402593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"448cc2f383bcd69d49b7aa547b5529f3c4d35dee","datavalue":{"value":{"amount":"+0.8403052","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":"Q987554$4905F633-95EF-494D-9E33-659A20188E1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"776f9ca932ff09ade5a460720302ddbe6f6a69ea","datavalue":{"value":{"entity-type":"item","numeric-id":5955205,"id":"Q5955205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"713717e88103cb35083b441b367deb42969e36df","datavalue":{"value":{"amount":"+0.8331063","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":"Q987554$00BCB26E-74F6-49B8-8C93-FFF31B8D3219","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb7e6ca95e3dd1924a840d198fd305b19ee82b58","datavalue":{"value":{"entity-type":"item","numeric-id":947724,"id":"Q947724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac1fb93741370b9cb3711cba32b9ef3f2f17b201","datavalue":{"value":{"amount":"+0.82609034","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":"Q987554$24D0949F-3444-4448-8007-429D72873C32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"697ad0792598d0470a7a65b50bf337688766fb3b","datavalue":{"value":{"entity-type":"item","numeric-id":653835,"id":"Q653835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c63393a9f6eac45cc9093062aa22f9b1d1b2ca57","datavalue":{"value":{"amount":"+0.8098728","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":"Q987554$E1BF05A4-4693-4CD4-9847-3284C74196E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf12b1822590debfd21bc3e87f560a056772e1ff","datavalue":{"value":{"entity-type":"item","numeric-id":5955201,"id":"Q5955201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9caa3c5f663138a4a7a4981a35ff48bc18cb0b9","datavalue":{"value":{"amount":"+0.7935683","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":"Q987554$6541754D-21F1-41AB-9BD4-D676BDE93E89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8d3c87370ec4b43d63fab375a79ceb4e69ae638","datavalue":{"value":{"entity-type":"item","numeric-id":3484869,"id":"Q3484869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbd0fc0b2e56df490d80f7c89cd1755b4b8710c2","datavalue":{"value":{"amount":"+0.77754515","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":"Q987554$D07B2B41-A18D-4ABF-94B1-73D300AB00FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"974029844f474defe5340255c51b6433fafa216b","datavalue":{"value":{"entity-type":"item","numeric-id":659608,"id":"Q659608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fe2db94324969819098e4a47fb48b302c992980","datavalue":{"value":{"amount":"+0.7691509","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":"Q987554$5FCD5E66-CF2B-41DF-B995-5B31AB35A56E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6249d3a7e5054dbd961bd20839497864fe7b33b1","datavalue":{"value":{"entity-type":"item","numeric-id":2563507,"id":"Q2563507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c6cc78faf3c0ef1067a0049f2a8941bf7934949","datavalue":{"value":{"amount":"+0.7659451","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":"Q987554$06F1A1AA-03A8-4A77-9334-5D209489358C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:987554","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:987554"}}}}}