Deciding the On-line Chromatic Number of a Graph with Pre-coloring is PSPACE-complete

Christian Kudahl

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

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.
OriginalsprogEngelsk
TitelAlgorithms and Complexity : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings
RedaktørerVangelis Th. Paschos, Peter Widmayer
ForlagSpringer
Publikationsdato2015
Sider313-324
ISBN (Trykt)978-3-319-18172-1
ISBN (Elektronisk)978-3-319-18173-8
DOI
StatusUdgivet - 2015
Begivenhed9th International Conference on Algorithms and Complexity: CIAC - Paris, Frankrig
Varighed: 20. maj 201522. maj 2015

Konference

Konference9th International Conference on Algorithms and Complexity
LandFrankrig
ByParis
Periode20/05/201522/05/2015
NavnLecture Notes in Computer Science
Vol/bind9079
ISSN0302-9743

Fingeraftryk

Dyk ned i forskningsemnerne om 'Deciding the On-line Chromatic Number of a Graph with Pre-coloring is PSPACE-complete'. Sammen danner de et unikt fingeraftryk.

Citationsformater