A bound for the game chromatic number of graphs

DOI10.1016/S0012-365X(98)00197-6zbMath0928.05022WikidataQ126550987 ScholiaQ126550987MaRDI QIDQ1297403

Thomas Dinski, Xuding Zhu

Publication date: 19 January 2000

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

treewidthacyclic chromatic numberplanar graphgame chromatic numberorientable genusseries parallel graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Games involving graphs (91A43) Coloring of graphs and hypergraphs (05C15)

Related Items

Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers ⋮ A simple competitive graph coloring algorithm. III ⋮ The graph distance game and some graph operations ⋮ Game brush number ⋮ PSPACE-hardness of two graph coloring games ⋮ Asymmetric coloring games on incomparability graphs ⋮ Bounds on the game transversal number in hypergraphs ⋮ Domination Game: A proof of the $3/5$-Conjecture for Graphs with Minimum Degree at Least Two ⋮ Generalised game colouring of graphs ⋮ The relaxed game chromatic index of \(k\)-degenerate graphs ⋮ Game chromatic index ofk-degenerate graphs ⋮ Impartial coloring games ⋮ PSPACE-completeness of two graph coloring games ⋮ The relaxed edge-coloring game and \(k\)-degenerate graphs ⋮ Graph colorings with restricted bicolored subgraphs: II. The graph coloring game ⋮ A connected version of the graph coloring game ⋮ An upper bound on the extremal version of Hajnal's triangle-free game ⋮ Lower bounds for the game colouring number of partial \(k\)-trees and planar graphs ⋮ Indicated coloring of the Mycielskian of some families of graphs ⋮ The strong game colouring number of directed graphs ⋮ Note on the game colouring number of powers of graphs ⋮ A note on the connected game coloring number ⋮ The game chromatic index of wheels ⋮ The game \(L(d,1)\)-labeling problem of graphs ⋮ A simple competitive graph coloring algorithm. II. ⋮ Indicated coloring game on Cartesian products of graphs ⋮ On forbidden subdivision characterizations of graph classes ⋮ The game chromatic index of some trees of maximum degree 4 ⋮ Indicated coloring of matroids ⋮ Efficient Graph Packing via Game Colouring ⋮ Refined activation strategy for the marking game ⋮ The game Grundy indices of graphs ⋮ Game chromatic number of Cartesian product graphs ⋮ The game of arboricity ⋮ Complete multipartite graphs and the relaxed coloring game ⋮ The incidence game chromatic number of paths and subgraphs of wheels ⋮ Weak acyclic coloring and asymmetric coloring games ⋮ The game chromatic index of forests of maximum degree \(\Delta \geqslant 5\) ⋮ The incidence game chromatic number of \((a,d)\)-decomposable graphs ⋮ Game coloring the Cartesian product of graphs ⋮ The eternal game chromatic number of random graphs ⋮ The 6-relaxed game chromatic number of outerplanar graphs ⋮ Lightness of digraphs in surfaces and directed game chromatic number ⋮ Colouring games on outerplanar graphs and trees ⋮ A simple competitive graph coloring algorithm ⋮ \textsf{PSPACE}-hardness of variants of the graph coloring game ⋮ Circular game chromatic number of graphs ⋮ On the game chromatic number of splitting graphs of path and cycle ⋮ The game coloring number of planar graphs ⋮ On game chromatic vertex-critical graphs

Cites Work

• On acyclic colorings of planar graphs
• The game coloring number of planar graphs
• Acyclic and oriented chromatic numbers of graphs
• An acyclic analogue to Heawood's theorem
• Game chromatic number of outerplanar graphs
• Radius two trees specify χ‐bounded classes
• The chromatic number of oriented graphs
• Acyclic colorings of planar graphs
• Unnamed Item
• Unnamed Item