The independence coloring game on graphs

DOI10.2989/16073606.2021.1947919MaRDI QIDQ5048907zbMATHOpenAlexFDO

Authors Boštjan Brešar, Daša Štesl

Publication date 16 November 2022

Published in Quaestiones Mathematicae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.13656

zbMATH Keywords

treegraph coloringgame chromatic numbercoloring gamecompetition-independence game

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: We propose a new coloring game on a graph, called the independence coloring game, which is played by two players with opposite goals. The result of the game is a proper coloring of vertices of a graph $G$, and Alice's goal is that as few colors as possible are used during the game, while Bob wants to maximize the number of colors. The game consists of rounds, and in round $i$, where $i=1,2,,ldots$, the players are taking turns in selecting a previously unselected vertex of $G$ and giving it color $i$ (hence, in each round the selected vertices form an independent set). The game ends when all vertices of $G$ are selected (and thus colored), and the total number of rounds during the game when both players are playing optimally with respect to their goals, is called the independence game chromatic number, $ch{i}_{ig}(G)$, of $G$. In fact, four different versions of the independence game chromatic number are considered, which depend on who starts a game and who starts next rounds. We prove that the new invariants lie between the chromatic number of a graph and the maximum degree plus $1$, and characterize the graphs in which each of the four versions of the game invariant equals $2$. We compare the versions of the independence game chromatic number among themselves and with the classical game chromatic number. In addition, we prove that the independence game chromatic number of a tree can be arbitrarily large.

Recommendations

• Infinite chromatic games
• A connected version of the graph coloring game
• Indicated coloring of graphs
• scientific article; zbMATH DE number 398953
• Game-perfect graphs

Cites work

• scientific article; zbMATH DE number 398953 (Why is no real title available?)
• Adapted game colouring of graphs
• Domination game and an imagination strategy
• Domination game and minimal edge cuts
• Efficient graph packing via game colouring
• Extremal problems for game domination number
• Game chromatic number of Cartesian product graphs
• Indicated coloring of graphs
• Majority coloring game
• ON THE COMPLEXITY OF SOME COLORING GAMES
• Online sum-paintability: the slow-coloring game
• The Map-Coloring Game
• The competition-independence game in trees
• The splittance of a graph

Cited in

(4)

• The competition-independence game in trees
• Chiraptophobic cockroaches evading a torch light.
• Infinite chromatic games
• On game chromatic vertex-critical graphs

This page was built for publication: The independence coloring game on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5048907)