Title | ||
---|---|---|
On Nordhaus-Gaddum type inequalities for the game chromatic and game coloring numbers. |
Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1016/j.disc.2019.01.012 | Discrete Mathematics |
Keywords | Field | DocType |
Nordhaus–Gaddum type inequalities,Coloring game,Marking game | Graph,Discrete mathematics,Combinatorics,Chromatic scale,Invariant (mathematics),Mathematics | Journal |
Volume | Issue | ISSN |
342 | 5 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Clément Charpentier | 1 | 0 | 0.34 |
Simone Dantas | 2 | 119 | 24.99 |
Celina M. H. de Figueiredo | 3 | 296 | 38.49 |
Ana Luísa Furtado | 4 | 0 | 0.34 |
Sylvain Gravier | 5 | 486 | 59.01 |