Online Coloring of Bipartite Graphs with and without Advice
In the online version of the well-known graph coloring problem, the vertices appear one after the other together with the edges to the already known vertices and have to be irrevocably colored immediately after their appearance. We consider this problem on bipartite, i.e., two-colorable graphs. We prove that at least ?1.13746?log2(n)?0.49887? colors are necessary for any deterministic online algorithm to be able to color any given bipartite graph on n vertices, thus improving on the previously known lower bound of ?log2 n?+1 for sufficiently large n.
online coloring bipartite graph lower bounds advice complexity