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 1.13747·log_2 n colors are necessary for any deterministic online algorithm to color any bipartite graph on n vertices, thus improving on the previously known lower bound of log_2 n + 1 for sufficiently large n. Recently, the advice complexity was introduced as a method for a fine-grained analysis of the hardness of online problems. We apply this method to the online coloring problem and prove (almost) tight linear upper and lower bounds on the advice complexity of coloring a bipartite graph online optimally or using 3 colors. Moreover, we prove that O(√n) advice bits are sufficient for coloring any graph on n vertices with at most ⌈log_2 n⌉ colors.
Online coloring of bipartite graphs with and without advice / M.P. Bianchi, H. Böckenhauer, J. Hromkovič, L. Keller - In: Computing and combinatorics : 18th annual international conference, COCOON 2012 : Sydney, Australia, august 20-22, 2012 : proceedingsBerlin : Springer, 2012. - ISBN 9783642322402. - pp. 519-530 (( Intervento presentato al 18. convegno Annual International Computing and Combinatorics Conference (COCOON) tenutosi a Sydney nel 2012.
Online coloring of bipartite graphs with and without advice
M.P. Bianchi;
2012
Abstract
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 1.13747·log_2 n colors are necessary for any deterministic online algorithm to color any bipartite graph on n vertices, thus improving on the previously known lower bound of log_2 n + 1 for sufficiently large n. Recently, the advice complexity was introduced as a method for a fine-grained analysis of the hardness of online problems. We apply this method to the online coloring problem and prove (almost) tight linear upper and lower bounds on the advice complexity of coloring a bipartite graph online optimally or using 3 colors. Moreover, we prove that O(√n) advice bits are sufficient for coloring any graph on n vertices with at most ⌈log_2 n⌉ colors.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.