On-line coloring and cliques covering for KK
s,t
-free graphs |
| |
Authors: | Iwona Cie?lik |
| |
Affiliation: | (1) Institute of Computer Science, Jagiellonian University, Nawojki 11, 30-072 Cracow, Poland |
| |
Abstract: | The problem of on-line coloring of an arbitrary graphs is known to be hard. Here we consider the problem of on-line coloring
in the simplified situation where the input graph is KKs,t-free. We show that the on-line coloring algorithm with the First Fit strategy of proposed by Capponi and Pilotto in 1] is the best one for KK1,t-free graphs (t≥3). A.Capponi and C.Pilotto have shown that this algorithm achieves a competitive ratio of t−1 while we show that it is the best possible. However for the family of KKs,t-free graphs (s≥2, t≥2) there exists no on-line coloring algorithm with a competitive function. The problem of an on-line cliques covering for
these families is hard. There exists no on-line cliques covering algorithm with a competitive function for the family of KKs,t-free graphs (s≥ 1, t≥3). The additional assumption that the input graph is given in a connected way does not help a lot and does not change our
results described above. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|