ONLINE AND FIRST-FIT COLORING OF GRAPHS THAT DO NOT INDUCE P-5

作     者：KIERSTEAD, HA PENRICE, SG TROTTER, WT 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：1995年第8卷第4期

页      面：485-498页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：ONLINE ALGORITHM GRAPH COLORING GREEDY ALGORITHM 

摘      要：For a graph H, let Forb(H) be the class of graphs that do not induce H, and let P-5 be the path on five vertices. In this article, we answer two questions of Gyarfas and Lehel. First, we show that there exists a function f(omega) such that for any graph G is an element of Forb(P-5), the on-line coloring algorithm First-Fit uses at most f(omega(G)) colors on G, where omega(G) is the clique size of G. Second, we show that there exists an on-line algorithm A that will color any graph G is an element of Forb(P-5) with a number of colors exponential in omega(G). Finally, we extend some of our results to larger classes of graphs defined in terms of a list of forbidden subgraphs.