## Abstrakt

In an on-line coloring, the vertices of a graph are revealed one by one. An algorithm assigns a color to each vertex after it is revealed. When a vertex is revealed, it is also revealed which of the previous vertices it is adjacent to. The on-line chromatic number of a graph, G, is the smallest number of colors an algorithm will need when on-line-coloring G. The algorithm may know G, but not the order in which the vertices are revealed. The problem of determining

if the on-line chromatic number of a graph is less than or equal to k, given a pre-coloring, is shown to be PSPACE-complete.

if the on-line chromatic number of a graph is less than or equal to k, given a pre-coloring, is shown to be PSPACE-complete.

Originalsprog | Engelsk |
---|---|

Titel | Algorithms and Complexity : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings |

Redaktører | Vangelis Th. Paschos, Peter Widmayer |

Forlag | Springer |

Publikationsdato | 2015 |

Sider | 313-324 |

ISBN (Trykt) | 978-3-319-18172-1 |

ISBN (Elektronisk) | 978-3-319-18173-8 |

DOI | |

Status | Udgivet - 2015 |

Begivenhed | 9th International Conference on Algorithms and Complexity: CIAC - Paris, Frankrig Varighed: 20. maj 2015 → 22. maj 2015 |

### Konference

Konference | 9th International Conference on Algorithms and Complexity |
---|---|

Land | Frankrig |

By | Paris |

Periode | 20/05/2015 → 22/05/2015 |

Navn | Lecture Notes in Computer Science |
---|---|

Vol/bind | 9079 |

ISSN | 0302-9743 |