ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • Indicated coloring game on Cartesian products of graphs
    Brešar, Boštjan ; Jakovac, Marko ; Mesarič Štesl, Daša
    The indicated coloring game is played on a simple graph ▫$G$▫ by two players, with a fixed set ▫$C$▫ of colors. In each round of the game Ann indicates an uncolored vertex, and Ben colors it using a ... color from ▫$C$▫, obeying just the proper coloring rule. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent this. The minimum cardinality of the set of colors ▫$C$▫ for which Ann has a winning strategy is called the indicated chromatic number, ▫$ \chi_i ( G )$▫, of a graph ▫$G$▫. In this paper, we prove that the indicated chromatic number of the Cartesian product ▫$G \square K_{n , m}$▫ is equal to 3 if ▫$\chi_i ( G ) = 3$▫. We also prove that ▫$\chi_i ( G \square T ) = \chi ( G )$▫, where ▫$G$▫ is a block graph and ▫$T$▫ is a tree. Indicated colorings in some other classes of Cartesian products of graphs are also studied. The investigations lead us to propose a Sabidussi-type equality as an open problem.
    Source: Discrete applied mathematics. - ISSN 0166-218X (Vol. 289, Jan. 2021, str. 320-326)
    Type of material - article, component part ; adult, serious
    Publish date - 2021
    Language - english
    COBISS.SI-ID - 41803267

    Link(s):

    https://www.sciencedirect.com/science/article/pii/S0166218X2030500X
    DOI

Shelf entry