ON THE COMPLEXITY OF SOME COLORING GAMES

DOI10.1142/S0129054191000091MaRDI QIDQ3988839zbMATH OpenOpenAlexFDO

Authors Hans L. Bodlaender

Publication date 28 June 1992

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054191000091

zbMATH Keywords

coloring gamescomplexitygraph algorithmsgraph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• scientific article; zbMATH DE number 139777
• The complexity of two colouring games
• The complexity of coloring games on perfect graphs
• The Parallel Complexity of Coloring Games
• The complexity of some graph colouring problems
• Colouring, constraint satisfaction, and complexity
• The complexity of grid coloring
• Coloring games on squares of graphs

Cited in

(only showing first 100 items - show all)

• Game-perfect graphs
• Lightness of digraphs in surfaces and directed game chromatic number
• Colouring games on outerplanar graphs and trees
• Circular game chromatic number of graphs
• Asymmetric directed graph coloring games
• The complexity of coloring games on perfect graphs
• Complexity of path-forming games
• The game coloring number of planar graphs
• Proper colouring painter-builder game
• On the game coloring index of \(F^+\)-decomposable graphs
• The matcher game played in graphs
• Majority coloring game
• On Nordhaus-Gaddum type inequalities for the game chromatic and game coloring numbers
• The game coloring number of planar graphs with a specific girth
• Indicated coloring of graphs
• Autoparatopism stabilized colouring games on rook's graphs
• Relaxed game chromatic number of trees and outerplanar graphs
• Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.
• Game-perfect digraphs
• The game chromatic number and the game colouring number of classes of oriented cactuses
• The game Grundy number of graphs
• The game coloring number of planar graphs with a given girth
• The incidence game chromatic number of \((a,d)\)-decomposable graphs
• Autotopism stabilized colouring games on rook's graphs
• Colored cut games
• Game chromatic number of strong product graphs
• On game chromatic vertex-critical graphs
• Game-perfect semiorientations of forests
• PSPACE-completeness of two graph coloring games
• A connected version of the graph coloring game
• Game chromatic number of some network graphs
• Game connectivity of graphs
• Indicated coloring game on Cartesian products of graphs
• The difference between game chromatic number and chromatic number of graphs
• Online coloring a token graph
• The orthogonal colouring game
• Mr. Paint and Mrs. Correct
• Proper 2-coloring game on some trees
• The edge coloring game on trees with the number of colors greater than the game chromatic index
• Lower bounds for the game colouring number of partial \(k\)-trees and planar graphs
• Refined activation strategy for the marking game
• The game of arboricity
• Weak acyclic coloring and asymmetric coloring games
• The game chromatic index of forests of maximum degree \(\Delta \geqslant 5\)
• On a vertex-edge marking game on graphs
• The complexity of two colouring games
• A note on the connected game coloring number
• Game chromatic index of \(k\)-degenerate graphs
• The Parallel Complexity of Coloring Games
• Transversal game on hypergraphs and the \(\frac{3}{4}\)-conjecture on the total domination game
• Colouring games
• Deciding the on-line chromatic number of a graph with pre-coloring is PSPACE-complete
• Evolutionary graph colouring
• Complexity of the game domination problem
• Bounds on the game transversal number in hypergraphs
• Equality perfect graphs and digraphs
• Game-perfect Graphs with Clique Number 2
• Efficient graph packing via game colouring
• Game coloring the Cartesian product of graphs
• Problems on cycles and colorings
• Impartial coloring games
• scientific article; zbMATH DE number 139777 (Why is no real title available?)
• Game chromatic number of graphs with locally bounded number of cycles
• Game chromatic number of outerplanar graphs
• Indicated coloring of matroids
• The game Grundy indices of graphs
• The independence coloring game on graphs
• The coloring game on matroids
• The coloring game on planar graphs with large girth, by a result on sparse cactuses
• On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs
• Colouring games based on autotopisms of Latin hyper-rectangles
• Game chromatic number of Cartesian and corona product graphs
• Paired-domination game played in graphs
• The incidence game chromatic number of paths and subgraphs of wheels
• Uniquely colorable graphs with equal chromatic and game chromatic numbers
• Vertex-edge marking score of certain triangular lattices
• Game chromatic number of toroidal grids
• The incidence game chromatic number
• Game chromatic number of toroidal grids
• The incidence game chromatic number
• Seurat games on Stockmeyer graphs
• Graph colorings with restricted bicolored subgraphs: II. The graph coloring game
• Abstract colorings, games and ultrafilters
• The complexity of grid coloring
• On monotonicity in maker-breaker graph colouring games
• The game chromatic index of wheels
• Indicated domination game
• Introduction to competitive graph coloring
• On graphs with maximum difference between game chromatic number and chromatic number
• The burning game on graphs
• The harmonious coloring game
• Game chromatic number of honeycomb related networks
• On game chromatic number of oriented network graphs
• Graph homomorphism, monotone classes and bounded pathwidth
• On the relaxed colouring game and the unilateral colouring game
• Decomposing a graph into forests
• Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers
• The complexity of constraint satisfaction games and QCSP
• The game chromatic number and the game colouring number of cactuses
• Generalised game colouring of graphs

This page was built for publication: ON THE COMPLEXITY OF SOME COLORING GAMES

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