scientific article; zbMATH DE number 139777

MaRDI QIDQ4028100zbMATH OpenFDO

Authors Hans L. Bodlaender

Publication date 28 March 1993

zbMATH Keywords

polynomial time algorithmsPSPACE-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Games involving graphs (91A43)

Recommendations

• ON THE COMPLEXITY OF SOME COLORING GAMES
• The complexity of coloring games on perfect graphs
• PSPACE-completeness of two graph coloring games
• A simple competitive graph coloring algorithm. III
• Two graph-colouring games

Cited in

(43)

• Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.
• Colouring games based on autotopisms of Latin hyper-rectangles
• Game theory on the blockchain: a model for games with smart contracts
• Colouring games
• Relaxed very asymmetric coloring games
• Coloring games on squares of graphs
• Adapted game colouring of graphs
• On the degree of trees with game chromatic number 4
• \textsf{PSPACE}-complete two-color planar placement games
• ON THE COMPLEXITY OF SOME COLORING GAMES
• The strong game colouring number of directed graphs
• Proper colouring painter-builder game
• Activation strategy for relaxed asymmetric coloring games
• Infinite chromatic games
• On caterpillars of game chromatic number 4
• Seurat games on Stockmeyer graphs
• Introduction to competitive graph coloring
• The connected greedy coloring game
• Fashion game on planar graphs
• Orderings on graphs and game coloring number
• A bound for the game chromatic number of graphs
• The complexity of two colouring games
• The eternal game chromatic number of random graphs
• The relaxed game chromatic index of \(k\)-degenerate graphs
• Mr. Paint and Mrs. Correct
• Deciding the on-line chromatic number of a graph with pre-coloring is PSPACE-complete
• Autoparatopism stabilized colouring games on rook's graphs
• An algorithmic analysis of the Honey-Bee game
• A simple competitive graph coloring algorithm. II.
• Bounded families for the on-line \(t\)-relaxed coloring
• The game chromatic index of some trees of maximum degree 4
• The Parallel Complexity of Coloring Games
• A simple competitive graph coloring algorithm. III
• The complexity of grid coloring
• A simple competitive graph coloring algorithm
• Complete multipartite graphs and the relaxed coloring game
• The complexity of coloring games on perfect graphs
• Online coloring a token graph
• \textsf{PSPACE}-hardness of variants of the graph coloring game
• PSPACE-hardness of two graph coloring games
• PSPACE-completeness of two graph coloring games
• Proper 2-coloring game on some trees
• Abstract colorings, games and ultrafilters

This page was built for publication:

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