Game chromatic number of some network graphs

DOI10.1007/S13226-020-0431-7MaRDI QIDQ2195643zbMATH OpenOpenAlexFDO

Authors R. Alagammai, V. Vijayalakshmi

Publication date 27 August 2020

Published in Indian Journal of Pure \& Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s13226-020-0431-7

zbMATH Keywords

butterfly graphscube-connected cyclesgame chromatic numbershuffle exchange network

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Games on graphs (graph-theoretic aspects) (05C57) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Games involving graphs (91A43)

Review text

Suppose that $G$ is a graph and $C$ is a set of colours. Alice and Bob play the following colouring game on $G$. Alice and Bob alternate their turns in colouring the vertices of $G$. At each turn, the player choose an uncoloured vertex $x$ and colour it with a colour from $C$ which is not used by any of the coloured neighbours of $x$. Alice has the first move. The game ends if no more moves are possible -- which happens if either all vertices are coloured, or there are uncoloured vertices, but for each of the uncoloured vertices, its coloured neighbours used all the colours. If at the end of the game, all the vertices are coloured, then Alice wins the game. Otherwise Bob wins. The game chromatic number of $G$, denoted by $\chi_g(G)$, is the least number of colours in the colour set $C$ so that Alice has a winning strategy. The authors of this paper determine the precise values of the $\chi_g$ of some interconnection network graph families such as: shuffle exchange network, cube-connected cycles and wrapped around butterflies. The entire exposition of the method of proof on each of the three instances is simple, neat and understandable.

Recommendations

• The Map-Coloring Game
• scientific article; zbMATH DE number 398953
• scientific article; zbMATH DE number 5670857
• A bound for the game chromatic number of graphs
• A simple competitive graph coloring algorithm. III

Cites work

• Game chromatic number of toroidal grids
• Layouts for the Shuffle-Exchange Graph Based on the Complex Plane Diagram
• ON THE COMPLEXITY OF SOME COLORING GAMES

Cited in

(10)

• Game chromatic number of generalized Petersen graphs and Jahangir graphs
• Game chromatic number of lexicographic product graphs
• The game chromatic and chromatic number of some graphs
• Game chromatic number of graphs with locally bounded number of cycles
• scientific article; zbMATH DE number 6843195 (Why is no real title available?)
• The Game Saturation Number of a Graph
• The game chromatic number of random graphs
• Game chromatic number of Cartesian product graphs
• Game list colouring of graphs
• Game chromatic index of graphs with given restrictions on degrees

This page was built for publication: Game chromatic number of some network graphs

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