Abstract | ||
---|---|---|
In the online graph coloring problem, vertices from a graph , known in advance, arrive in an online fashion and an algorithm must immediately assign a color to each incoming vertex so that the revealed graph is properly colored. The exact location of in the graph is not known to the algorithm, since it sees only previously colored neighbors of . The of is the smallest number of colors such that some online algorithm is able to properly color for any incoming order. We prove that computing the online chromatic number of a graph is PSPACE-complete. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1007/s00224-017-9797-2 | international workshop on combinatorial algorithms |
Keywords | DocType | Volume |
PSPACE-completeness,Online coloring,Online chromatic number | Conference | 62 |
Issue | ISSN | Citations |
6 | 1432-4350 | 2 |
PageRank | References | Authors |
0.47 | 7 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Martin Böhm | 1 | 29 | 6.65 |
Pavel Veselý | 2 | 30 | 9.05 |