The incidence game chromatic number

Andres, Dominique (2009) The incidence game chromatic number.
Published in: Discrete Applied Mathematics Vol. 157 (9). pp. 1980-1987.

Abstract

We introduce the incidence game chromatic number which unifies the ideas of game chromatic number and incidence coloring number of an undirected graph. For k-degenerate graphs with maximum degree D, the upper bound 2D+4k-2 for the incidence game chromatic number is given. If D is at least 5k, we improve this bound to the value 2D+3k-1. We also determine the exact incidence game chromatic number of cycles, stars and sufficiently large wheels and obtain the lower bound 3D/2 for the incidence game chromatic number of graphs of maximum degree D.


Actions:
Download: [img] Postscript - Preprinted Version
Download (301Kb) | Preview
Download: [img] PDF - Preprinted Version
Download (134Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 6 (Google Scholar) |
Uncontrolled Keywords: incidence coloring number game chromatic number k-degenerate graph star wheel cycle game chromatic index
Subjects:
  • 91-XX Game theory, economic, social and behavioral sciences > 91Axx Game theory > 91A05 2-person games

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C15 Coloring of graphs and hypergraphs

    		•
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader
    Mathematical Institute > Prof. Dr. Faigle
    Related URLs:
    Deposit Information:
    ZAIK Number: zaik2007-565
    Depositing User: Dominique Andres
    Date Deposited: 04 Dec 2007 00:00
    Last Modified: 19 Dec 2011 09:44
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/565