On characterizing game-perfect graphs by forbidden induced subgraphs

Authors

  • Stephan Dominique Andres

DOI:

https://doi.org/10.11575/cdm.v7i1.62115

Abstract

A graph G is called g-perfect if, for any induced subgraph H of G, the game chromatic number of H equals the clique number of H. A graph G is called g-col-perfect if, for any induced subgraph H of G, the game coloring number of H equals the clique number of H. In this paper we characterize the classes of g-perfect resp. g-col-perfect graphs by a set of forbidden induced subgraphs and explicitly. Moreover, we study similar notions for variants of the game chromatic number, namely B-perfect and [A,B]-perfect graphs, and for several variants of the game coloring number, and characterize the classes of these graphs.

Downloads

Published

2012-04-23

Issue

Section

Articles