Asymmetric coloring games on incomparability graphs

DOI10.1016/j.endm.2015.06.108zbMath1346.05188arXiv1503.04748OpenAlexW2964186404MaRDI QIDQ324375

Tomasz Krawczyk, Bartosz Walczak

Publication date: 14 October 2016

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1503.04748

zbMATH Keywords

intersection graphchromatic numbertriangle-freegame chromatic numberline segmentsincomparability graphsGrundy number

Mathematics Subject Classification ID

Games involving graphs (91A43) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Online algorithms; streaming algorithms (68W27) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (5)

PSPACE-hardness of two graph coloring games ⋮ PSPACE-completeness of two graph coloring games ⋮ Deciding the On-line Chromatic Number of a Graph with Pre-coloring Is PSPACE-Complete ⋮ The connected greedy coloring game ⋮ Conflict-free coloring of string graphs

Cites Work

• Unnamed Item
• Activation strategy for asymmetric marking games
• A bound for the game chromatic number of graphs
• The game coloring number of planar graphs
• A simple competitive graph coloring algorithm
• The game Grundy number of graphs
• The game coloring number of pseudo partial \(k\)-trees
• Lower bounds for the game colouring number of partial \(k\)-trees and planar graphs
• Refined activation strategy for the marking game
• Very asymmetric marking games
• An Effective Version of Dilworth's Theorem
• ON THE COMPLEXITY OF SOME COLORING GAMES
• Game chromatic number of outerplanar graphs
• Radius two trees specify χ‐bounded classes
• Asymmetric graph coloring games
• First-Fit Coloring of Incomparability Graphs

This page was built for publication: Asymmetric coloring games on incomparability graphs