pipette
ESEspañol

Connected Coloring Games on Corona Products of Graphs

Da\v{s}a Mesari\v{c} \v{S}tesl

Preprint

In the authors' words

We study the connected coloring game on corona products of graphs. For connected graphs and , we prove the sharp upper bound and establish a further bound using the Bob-start ordinary coloring game on the second factor. We show that the difference between the Alice-start and Bob-start connected game chromatic numbers can be arbitrarily large in either direction. We further prove that a connected subgraph may have arbitrarily larger connected game chromatic number than its ambient connected graph, and that cannot be bounded in terms of and alone, even when both factors have connected game chromatic number . We also obtain corona products for which the difference is arbitrarily large and construct infinitely many connected graphs with . Finally, for corona products of trees, we prove the universal upper bound , characterize those attaining the value , give structural sufficient conditions for the value , and exhibit a broad family attaining the value .

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.