E-viri
Recenzirano
Odprti dostop
-
Charpentier, Clément; Dantas, Simone; de Figueiredo, Celina M.H.; Furtado, Ana; Gravier, Sylvain
Discrete mathematics, 20/May , Letnik: 342, Številka: 5Journal Article
A seminal result by Nordhaus and Gaddum states that 2n≤χ(G)+χ(G¯)≤n+1 for every graph G of order n, where G¯ is the complement of G and χ is the chromatic number. We study similar inequalities for χg(G) and colg(G), which denote, respectively, the game chromatic number and the game coloring number of G. Those graph invariants give the score for, respectively, the coloring and marking games on G when both players use their best strategies.
