Add to ORKGThere are many open problems and conjectures of P.Erdoes dealing with the relation between the chromatic number of a graph and the structure of its cycle lengths. We present a polynomial time vertex-colouring algorithm called MAXBIP which either find a proper vertex k-colouring for a given graph G or constructs a sequence of cycles in G of at least [(k-1)/(2)] different odd cycle lengths and of at least [(k-2)/(2)] different even cycle lengths. As a corollary we obtain the following solution of a problem of B. Bollobas and P. Erdoes [4]: Let C_o(G) and C_e(G) denote the set of odd cycle lengths and even cycle lengths in a graph G, respectively. Let vertical stroke C_o(G) vertical stroke =r and vertical stroke C_e(G) vertical stroke =s, then...