On-line coloring of I s -free graphs and co-planar graphs
Iwona CieMarcin Kozik, Piotr Micek · 2006
An on-line vertex coloring algorithm receives vertices of a graph in some externally determined order. Each new vertex is presented together with a set of the edges connecti ng it to the previously presented vertices. As a vertex is presented, the algorithm assigns it a color which cannot be c hanged afterwards. The on-line coloring problem was addressed for many different classes of graphs defined in ter ms of forbidden structures. We analyze the class of Is