Counterexample to a conjecture of Gyori on C-2l-free bipartite graphs

Note Counterexample to a conjecture of Györi on C2l-free bipartite graphs夡 C. Balbuenaa, P. García-Vázquezb, X. Marcotea, J.C. Valenzuelac aDepartament de Matemàtica Aplicada III, Universitat Politècnica de Catalunya, Campus Nord, Edifici C2, C/ Jordi Girona1i3, E-08034 Barcelona, Spain bDepartamento de Matemática Aplicada I, Universidad de Sevilla, Avda Reina Mercedes 2, E-41012 Sevilla, Spain cDepartamento de Matemáticas, Universidad de Cádiz, Avda Ramón Puyol s/n, E-11202 Cádiz, Spain Abstract A counterexample on a conjecture of Györi related with C2l -free bipartite graphs is described. Keywords: Cycles in bipartite graphs; Forbidden subgraphs In 1997 Györi [2] studied the structure of C6-free bipartite graphs and the relationship between this problem and some interesting results of Erdös et al. [1] on a number-theoretic problem. Namely, Györi proved a conjecture of Erdös et al. [1] regarding the maximum number of edges that a C6-free bipartite graph can have. Moreover, he proved another theorem that generalizes the previous one for cycles of longer length. In this paper Györi stated a conjecture [2, p. 373] that apparently contains a misprint1and it should have been expressed in this way: Conjecture 1. If G=(X, Y ) is a bipartite graph with color classes X, Y where |X|=m, |Y|=n,m2⩽n,3⩽l⩽m and Ghas at least (l −1)n +m−l+2 edges, then Gmust contain a cycle of length 2l. In a recent paper [3], the same author disproves Conjecture 1 for l=3, but leaves the proof or refutation for l⩾4 as an open problem. In this note we provide a counterexample that disproves Conjecture 1 when m⩾2l−1. Let us denote by K(m,n) the complete bipartite graph with mvertices in the first class and nvertices in the second one. Let us also denote by dG(v) the degree of the vertex vin the graph G. Let l,m be integers such that 3⩽l⩽2(l −1)⩽m. We consider the graphs G1=K(m−l+1,l−1)and G2=K(l−1,n−l+2). Take two vertices u∈V(G 1)and v∈V(G 2)with dG1(u) =m−l+1 and dG2(v) =l−1, and let Gbe the bipartite 夡Research supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund (ERDF) under project MTM2005-08990-C02-02. E-mail addresses: m.camino.balb[email protected] (C. Balbuena), pgv[email protected] (P. García-Vázquez), francisco.javier[email protected] (X. Marcote), jcarlos.v[email protected] (J.C. Valenzuela). 1 The original conjectured value (l − 1)n + m − l + 1 (see [2]) may be easily disproved by means of a graph roughly outlined by the author. We appreciate the referee’s comments enlightening this misprint. 0012-365X/$ doi:10.1016/j.disc.2006.07.003 C. Balbuena et al./Discrete Mathematics 307 (2007) 748 –749 749 u... v... u = v G1=K3,2 G2=K2,24 G Fig. 1. The graph Gwith l=3,m=5 and n=25. graph on mand nvertices obtained by gluing the graphs G1and G2in such a way that the vertex uof G1is identified with the vertex vof G2(see Fig. 1). Clearly, any cycle of Gmust be entirely contained in either G1or G2. But Gi,i=1,2, cannot contain a cycle of length 2lbecause one of its classes has cardinality l−1. So Gis free of C2land it has size e(G) =(m −l+1) (l −1)+(l −1)(n −l+2)⩾(l −1)n +m−l+2 because m⩾2l−1. Therefore, Conjecture 1 is disproved for m⩾2l−1. In [2], Györi proved the following result: Theorem. If G(X, Y ) is a bipartite graph with color classes X, Y such that |X|=m,|Y|=n,m2⩽nand G has at least (l −1)n +c(l)m2edges for some constant c(l) then G must contain a cycle of length 2l. Thus, we propose the following reformulation of the conjecture: Conjecture 2. If G=(X, Y ) is a bipartite graph with color classes X, Y where |X|=m, |Y|=n,m2⩽n,3⩽l⩽m such that m>(l−1)2and Ghas at least (l −1)n +1/(l −1)m2edges then Gmust contain a cycle of length 2l. Corollary of Theorem 1 in [3] confirms our Conjecture 2 for l=3. For l⩾4 it is still an open problem. References [1] P. Erdös, A. Sarközy, V.T. Sós, On product representation of powers I, European J. Combin. 16 (1995) 567–588. [2] E. Györi, C6-free bipartite graphs and product representation of squares, Discrete Math. 165/166 (1997) 371–375. [3] E. Györi, Triangle-free hypergraphs, Combinatorics, Probab. Comput. 15 (1–2) (2006) 185–191.