The complexity of coloring games on perfect graphs

DOI10.1016/0304-3975(92)90254-DzbMath0785.90119OpenAlexW2069107705WikidataQ59568011 ScholiaQ59568011MaRDI QIDQ1202928

Hans L. Bodlaender, Dieter Kratsch

Publication date: 22 April 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90254-d

zbMATH Keywords

polynomial time algorithmbipartite graphsperfect graphssplit graphsNP-hardnesscoloring gamesinterval graphsPSPACE-completenesswinning strategycoNP-hardnessgreedy-like strategy

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) 2-person games (91A05) Games involving graphs (91A43)

Related Items (2)

Finding hidden independent sets in interval graphs ⋮ Game chromatic number of generalized Petersen graphs and Jahangir graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• PSPACE-Hardness of some combinatorial games
• Complexity of problems in games, graphs and algebraic equations
• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• On the complexity of some two-person perfect-information games
• The NP-completeness column: an ongoing guide
• Planar Formulae and Their Uses
• ON THE COMPLEXITY OF SOME COLORING GAMES
• Design and implementation of an efficient priority queue

This page was built for publication: The complexity of coloring games on perfect graphs