| Autor: |
Furtado, Ana Luísa C., Palma, Miguel A.D.R., Dantas, Simone, de Figueiredo, Celina M.H., Furtado, Ana Luísa C., Palma, Miguel A.D.R., Dantas, Simone, de Figueiredo, Celina M.H. |
| Zdroj: |
RAIRO - Operations Research; September 2023, Vol. 57 Issue: 5 p2757-2767, 11p |
| Abstrakt: |
The coloring game is played by Alice and Bob on a finite graph G. They take turns properly coloring the vertices with t colors. The goal of Alice is to color the input graph with t colors, and Bob does his best to prevent it. If at any point there exists an uncolored vertex without available color, then Bob wins; otherwise Alice wins. The game chromatic number χg(G) of Gis the smallest number tsuch that Alice has a winning strategy. In 1991, Bodlaender showed the smallest tree Twith χg(T) equal to 4, and in 1993 Faigle et al.proved that every tree Tsatisfies the upper bound χg(T)≤4. The stars T= K1,pwith p≥ 1 are the only trees satisfying χg(T) = 2; and the paths T= Pn, n≥ 4, satisfy χg(T) = 3. Despite the vast literature in this area, there does not exist a characterization of trees with χg(T) = 3 or 4. We answer a question about the required degree to ensure χg(T) = 4, by exhibiting infinitely many trees with maximum degree 3 and game chromatic number 4. |
| Databáze: |
Supplemental Index |
| Externí odkaz: |
|
