On Nordhaus-Gaddum type inequalities for the game chromatic and game coloring numbers

被引：2
|
作者：
Charpentier, Clement [1 ]
Dantas, Simone [2 ]
de Figueiredo, Celina M. N. [3 ]
Furtado, Ana [4 ]
Gravier, Sylvain [5 ]
机构：
[1] Univ Grenoble Alpes, Grenoble, France
[2] Univ Fed Fluminense, IME, Niteroi, RJ, Brazil
[3] Univ Fed Rio de Janeiro, COPPE, Rio De Janeiro, Brazil
[4] Univ Fed Rio de Janeiro, CEFET RJ COPPE, Rio De Janeiro, Brazil
[5] Univ Grenoble Alpes, CNRS, Grenoble, France
来源：
DISCRETE MATHEMATICS | 2019年 / 342卷 / 05期
关键词：
Nordhaus-Gaddum type inequalities; Coloring game; Marking game; GRAPHS;
D O I：
10.1016/j.disc.2019.01.012
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A seminal result by Nordhaus and Gaddum states that 2 root n <= chi(G) + chi((G) over bar) <= n + 1 for every graph G of order n, where (G) over bar is the complement of G and chi is the chromatic number. We study similar inequalities for chi(g)(G) and col(g)(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. (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页码：1318 / 1324
页数：7
相关论文
共 14 条
12