HAL-Inria | Publications, software ... of Inria's scientists |

In the paper an analogous problem for bipartite graphs is considered. It is proved that every bipartite graph with color classes of cardinalities m and n, m <= n, and size greater than n(m - k - 1) + k + 1 contains a cycle of length 2m - 2k, where m >= 1/2k(2) + 3/2k + 4, k is an element of N. The bound on the number of edges is best possible. Moreover, this size condition guarantees the existence of cycles of all even lengths up to 2m - 2k. We also characterize all extremal graphs for this problem. Finally, we conjecture that the condition on the order may be relaxed to m >= 2k + 2.

Cited literature [7 references]

https://hal.inria.fr/hal-00988212

Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>

Submitted on : Wednesday, May 7, 2014 - 4:21:42 PM

Last modification on : Wednesday, November 29, 2017 - 10:26:17 AM

Document(s) archivé(s) le : Thursday, August 7, 2014 - 11:40:22 AM

Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>

Submitted on : Wednesday, May 7, 2014 - 4:21:42 PM

Last modification on : Wednesday, November 29, 2017 - 10:26:17 AM

Document(s) archivé(s) le : Thursday, August 7, 2014 - 11:40:22 AM