arXiv Open Access 2014

Deciding the On-line Chromatic Number of a Graph with Pre-Coloring is PSPACE-Complete

Christian Kudahl

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.CC math.CO

Penulis (1)

Christian Kudahl

Format Sitasi

APA MLA BibTeX

Kudahl, C. (2014). Deciding the On-line Chromatic Number of a Graph with Pre-Coloring is PSPACE-Complete. https://arxiv.org/abs/1406.1623

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2014
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓