scientific article

zbMath0770.90098MaRDI QIDQ4028100

Hans L. Bodlaender

Publication date: 28 March 1993

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

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)

Related Items

A simple competitive graph coloring algorithm. III ⋮ PSPACE-hardness of two graph coloring games ⋮ On caterpillars of game chromatic number 4 ⋮ The relaxed game chromatic index of \(k\)-degenerate graphs ⋮ Game theory on the blockchain: a model for games with smart contracts ⋮ PSPACE-completeness of two graph coloring games ⋮ Coloring games on squares of graphs ⋮ Adapted game colouring of graphs ⋮ On the degree of trees with game chromatic number 4 ⋮ The strong game colouring number of directed graphs ⋮ The connected greedy coloring game ⋮ A simple competitive graph coloring algorithm. II. ⋮ The game chromatic index of some trees of maximum degree 4 ⋮ Complete multipartite graphs and the relaxed coloring game ⋮ The eternal game chromatic number of random graphs ⋮ Relaxed very asymmetric coloring games ⋮ Activation strategy for relaxed asymmetric coloring games ⋮ Infinite chromatic games ⋮ A simple competitive graph coloring algorithm ⋮ \textsf{PSPACE}-hardness of variants of the graph coloring game ⋮ Bounded families for the on-line \(t\)-relaxed coloring ⋮ A bound for the game chromatic number of graphs