{"entities":{"Q868335":{"pageid":870183,"ns":120,"title":"Item:Q868335","lastrevid":50042368,"modified":"2026-01-12T18:55:49Z","type":"item","id":"Q868335","labels":{"en":{"language":"en","value":"Counterexample to a conjecture of Gy\u00f6ri on \\(C_{2l}\\)-free bipartite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5130430"}},"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":"Q868335$F076114A-42F6-4AE0-A589-99E45A6E5677","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9f47a06e9e8e2f478c886a26ea40f6906c722e30","datavalue":{"value":{"text":"Counterexample to a conjecture of Gy\u00f6ri on \\(C_{2l}\\)-free bipartite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q868335$BFBEF8B4-7753-4E99-9401-F19AEA25BDDD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"30cb5c079928c078cc1614c22f17f6a42a474b7b","datavalue":{"value":"1124.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868335$36C6A537-7870-4549-853C-BF70DCE645E1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868335$28F75277-17A0-4B6A-BDD5-8F2398505F19","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3af4457e51d097fa27d84537ba93ffccbacd245f","datavalue":{"value":{"time":"+2007-03-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q868335$8618327D-CDB9-4C62-A7A2-E74E517E65F3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f26bc40a4b518440adffac4a8d27e5b2fb0775a5","datavalue":{"value":"\\textit{E. Gy\u00f6ri} [Discrete Math. 165/166, 371--375 (1997; Zbl 0873.05058)] stated the following conjecture:  Conjecture~1. If \\(G=(X,Y)\\) is a bipartite graph with color classes \\(X\\),\\(Y\\), where \\(| X| =m\\), \\(| Y| =n\\), \\(m2\\leq n\\), \\(3\\leq l\\leq m\\) and \\(G\\) has at least \\((l-1)n+m-l+2\\) edges, then \\(G\\) must contain a cycle of length \\(2l\\).   The current note provides a counterexample that disproves Conjecture~1 when \\(m\\geq 2l-1\\). The following reformulation of Conjecture~1 is proposed:   Conjecture~2. If \\(G=(X,Y)\\) is a bipartite graph with color classes \\(X\\),\\(Y\\), where \\(| X| =m\\), \\(| Y| =n\\), \\(m2\\leq n\\), \\(3\\leq l\\leq m\\) such that \\(m>(l-1)2\\) and \\(G\\) has at least \\((l-1)n+1/(l-1)m2\\) edges, then \\(G\\) must contain a cycle of length \\(2l\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q868335$050560B0-4FFF-4C4B-A727-13120BC72202","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868335$942CF02A-A853-43D4-BBA7-EB5B694C9665","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"10702b3a4713d20880646897947956445204471e","datavalue":{"value":"5130430","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868335$BA1C9740-CA09-4DC7-8D76-A94DC27304A5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dcf267cbc3e04fdcfc3d3761f7ad8ebdabe8c51","datavalue":{"value":"cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q868335$D2348825-95A2-4305-BAB9-9E027D661E6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eecb173004633ca38efc326bcd073800d8b745c9","datavalue":{"value":"bipartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q868335$C7092D34-4E55-45AB-8F11-215133DE0E18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"453a43e7e93d9a367957c940a4dbc5498dddc3ee","datavalue":{"value":"forbidden subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q868335$433A3A9F-D9C5-46E6-B817-40FFF6C89F8D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f3bc0304c0688036fad9ef981dca7aa0b0cd5e6f","datavalue":{"value":{"entity-type":"item","numeric-id":270264,"id":"Q270264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868335$B68A954F-80D3-449F-9EE9-D521E00EBF1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"50974e03e6cfed6fc8d71438aa01aa601a6f48c8","datavalue":{"value":{"entity-type":"item","numeric-id":644635,"id":"Q644635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868335$F8340967-E79C-4953-B65B-DEE5F5E9DF2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"89484886d383b7d167cc93ce2619973f152b9028","datavalue":{"value":{"entity-type":"item","numeric-id":932600,"id":"Q932600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868335$0129C93C-7122-44D9-BF55-AFFBF48DF2BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"31282650d3109a929109f3ead29486b4b9027afa","datavalue":{"value":{"entity-type":"item","numeric-id":1684256,"id":"Q1684256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868335$5C933B3B-AB95-460E-BAE1-A432617CD6D4","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":"Q868335$D48A9625-EF53-4171-A98D-D18D7DD41533","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"42c6ec13f86a78afe4bfaa62c95aa757e226bae7","datavalue":{"value":"https://doi.org/10.1016/j.disc.2006.07.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q868335$6E4CFFDD-0ACA-4606-B79E-54E99CE41B28","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"89095ceac4e7234691ee655b6fd95fb7d1015632","datavalue":{"value":"W2027076080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868335$5CF095B7-BDDE-4C9A-9939-BFC1C98AA035","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee6cf8f5df4e8a9fa5d626bba42ffc310386c6d0","datavalue":{"value":{"entity-type":"item","numeric-id":1902964,"id":"Q1902964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868335$C4D41EAA-C92C-47DC-B6E6-382BF3153F48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3f4d077221dded56e0b99cd034aa37d274516a5","datavalue":{"value":{"entity-type":"item","numeric-id":1356758,"id":"Q1356758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868335$6567F107-AC22-4A2A-9433-325CD07BD307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbf4cc9f7c6a1691f607696275a1d1877179d815","datavalue":{"value":{"entity-type":"item","numeric-id":3373663,"id":"Q3373663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868335$8F71D3DE-61FA-456F-B6D2-7AAC96E3EDD4","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"2a2dd9dc4b6858ffa4687f244e22a6c0fab2750c","datavalue":{"value":"Q122973139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868335$C4B6970B-5469-422E-ADEE-4B36057EE6F0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3d183466a207da9d7e63c07db4536740dc2bdd66","datavalue":{"value":"10.1016/J.DISC.2006.07.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868335$1118DE41-880C-467C-8530-0E337A3FB3C4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9750fd72b2d21393aba61a59c9af78ae885d9dd3","datavalue":{"value":{"entity-type":"item","numeric-id":4667796,"id":"Q4667796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"505d74d692fbf5a6f4af0fdd384f889ac1f72b49","datavalue":{"value":{"amount":"+0.769226610660553","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":"Q868335$612089C5-43E3-40F8-B7C1-B788251BFB57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1513d37cd53d875673d86ae3eaea8f75dc8fd27","datavalue":{"value":{"entity-type":"item","numeric-id":3025210,"id":"Q3025210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55715a8edc6a13329dd5504478dcdb5888d82cee","datavalue":{"value":{"amount":"+0.7499415278434753","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":"Q868335$1584E3B9-83C2-4806-907E-F3E15C97B6F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d2f23854e1e04852e6f5eceed1077727028f6bd","datavalue":{"value":{"entity-type":"item","numeric-id":4262234,"id":"Q4262234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17866215b8cd2808463819d7f5be4588f5e140c1","datavalue":{"value":{"amount":"+0.7489190101623535","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":"Q868335$F27782DF-CB53-44E0-9D86-A9CACDB3C3C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46d6373200294d888d4470fc5552e952500dd07e","datavalue":{"value":{"entity-type":"item","numeric-id":6080869,"id":"Q6080869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"198cd1c8df2e46f6d4b09412a9d1869e9e00d0a3","datavalue":{"value":{"amount":"+0.7475873231887817","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":"Q868335$6402A421-B64E-4186-81E7-FDE1F265EB25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3882fcc35ef4836625c1f13d517a24f5d2aa40da","datavalue":{"value":{"entity-type":"item","numeric-id":2563427,"id":"Q2563427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d63a1689407e668ef2ad8e546f25711bf63c935","datavalue":{"value":{"amount":"+0.7445862293243408","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":"Q868335$6426250A-9423-438D-B5BF-9724D8432A5B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:868335","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:868335"}}}}}