Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Online Coloring Known Graphs. | Online Coloring Known Graphs Magnus M. Halldórsson Science Institute - University of Iceland IS-107 Reykjavik Iceland mmh@ mmh. Submitted September 13 1999 Accepted February 24 2000. Subject Classification 05C15 68W25. Keywords graph coloring online algorithms. Abstract The problem of online coloring an unknown graph is known to be hard. Here we consider the problem of online coloring in the relaxed situation where the input must be isomorphic to a given known graph. All that foils a computationally powerful player is that it is not known to which sections of the graph the vertices to be colored belong. We show that the performance ratio of any online coloring algorithm with advance knowledge of the input graph is at least Q N log2 N where N is the number of vertices. This matches and generalizes the bound for the case of an unknown input graph. We also show that any online independent set algorithm has a performance ratio at least N 8. 1 Online Graph Coloring Graph coloring is the problem of assigning the fewest possible colors to the vertices of a graph so that adjacent vertices receive different colors. In the online version the input graph is given only one vertex at a time along with the edges to previous vertices and the algorithm must irrevocably color the given vertex before receiving later ones. The Known-Graph Online Model Online problems receive much of their difficulty from the fact that the input is hidden. Clearly if the whole input sequence was given the problem reduces to the offline version. But what if the input was known but not the sequence in which it was given In the case of graphs suppose 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 7 2000 R7 2 the input had to induce a graph isomorphic to a graph known in advance but the identification of the presented vertices was not given. Can we then color the graph relatively easily Formally consider the following game for two players Alice and Bob. 1. Alice presents Bob with a graph G on N
