On game chromatic vertex-critical graphs

DOI10.1007/S40840-022-01418-6zbMATH Open1504.05191arXiv2105.09674OpenAlexW3162632569MaRDI QIDQ2107136FDOQ2107136

Daša Štesl, Marko Jakovac

Publication date: 1 December 2022

Published in: Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

Abstract: Several games that arise from graph coloring have been introduced and studied. Let $varphi$ denote a graph invariant that arises from such a game. If $G$ is a graph and $varphi(G-x)eqvarphi(G)=k$, $kgeq1$, holds true for every vertex $xinV(G)$, then $G$ is called a $k$-$varphi$-game-vertex-critical graph. We study the concept of $varphi$-game-vertex-criticality for $varphiinch{i}_g,ch{i}_i,ch{i}_{ig}^A,ch{i}_{ig}^{AB}$, where $ch{i}_g$ denotes the standard game chromatic number, $ch{i}_i$ denotes the indicated game chromatic number and $ch{i}_{ig}^A$, $ch{i}_{ig}^{AB}$ denote two versions of the independence game chromatic number. Since the game chromatic number $varphi(G-x)$ can either decrease or increase with respect to $varphi(G)$, we distinguish between lower, upper and mixed vertex-criticality. We show that for $varphiinch{i}_g,ch{i}_{ig}^A,ch{i}_{ig}^{AB}$ the difference $varphi(G)-varphi(G-x)$, $xinV(G)$, can be arbitrarily large. A characterization of $2$-$varphi$-game-vertex-critical and (connected) $3$-$varphi$-lower-game-vertex-critical graphs for all $varphiinch{i}_g,ch{i}_i,ch{i}_{ig}^A,ch{i}_{ig}^{AB}$ is given. It is shown that $ch{i}_g$-game-vertex-critical, $ch{i}_{ig}^A$-game-vertex-critical and $ch{i}_{ig}^{AB}$-game-vertex-critical graphs are not necessarily connected. However, it is also shown that $ch{i}_i$-lower-game-vertex-critical graphs are always connected.

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

Recommendations

• On indicated chromatic number of graphs
• The independence coloring game on graphs
• A new game chromatic number
• Infinite chromatic games
• The game chromatic and chromatic number of some graphs

zbMATH Keywords

game chromatic numbergame coloringvertex-criticalityindependence game chromatic numberindicated game chromatic number

Mathematics Subject Classification ID

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

Cites Work

• Domination Game and an Imagination Strategy
• Title not available (Why is that?)
• Title not available (Why is that?)
• Indicated coloring of matroids
• A bound for the game chromatic number of graphs
• Title not available (Why is that?)
• The Map-Coloring Game
• Competitive colorings of oriented graphs
• On the oriented game chromatic number
• Domination game critical graphs
• ON THE COMPLEXITY OF SOME COLORING GAMES
• Colouring games
• Efficient Graph Packing via Game Colouring
• Majority coloring game
• Adapted game colouring of graphs
• Indicated coloring of graphs
• The game of arboricity
• The game chromatic number of trees and forests
• Incidence Coloring Game and Arboricity of Graphs
• The incidence game chromatic number
• On indicated chromatic number of graphs
• On indicated coloring of graphs
• Game total domination critical graphs
• Indicated coloring game on Cartesian products of graphs
• Title not available (Why is that?)
• The independence coloring game on graphs

This page was built for publication: On game chromatic vertex-critical graphs

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