DOAJ Open Access 2015

The game chromatic number of trees and forests

Charles Dunn Victor Larsen Kira Lindke Troy Retter Dustin Toci

Lihat Sumber DOI

Abstrak

While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests with game chromatic number 3 and 4. In doing so, we present a minimal example of a forest with game chromatic number 4, criteria for determining in polynomial time the game chromatic number of a forest without vertices of degree 3, and an example of a forest with maximum degree 3 and game chromatic number 4. This gives partial progress on the open question of the computational complexity of the game chromatic number of a forest.

Topik & Kata Kunci

Mathematics

Penulis (5)

Charles Dunn

Victor Larsen

Kira Lindke

Troy Retter

Dustin Toci

Format Sitasi

APA MLA BibTeX

Dunn, C., Larsen, V., Lindke, K., Retter, T., Toci, D. (2015). The game chromatic number of trees and forests. https://doi.org/10.46298/dmtcs.2130

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.2130

Informasi Jurnal

Tahun Terbit: 2015
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.2130
Akses: Open Access ✓