Asymmetric coloring games on incomparability graphs

DOI10.1007/978-3-662-43948-7_61zbMATH Open1346.05188arXiv1503.04748OpenAlexW2964186404MaRDI QIDQ324375FDOQ324375

Tomasz Krawczyk, Bartosz Walczak

Publication date: 14 October 2016

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

Abstract: Consider the following game on a graph $G$: Alice and Bob take turns coloring the vertices of $G$ properly from a fixed set of colors; Alice wins when the entire graph has been colored, while Bob wins when some uncolored vertices have been left. The game chromatic number of $G$ is the minimum number of colors that allows Alice to win the game. The game Grundy number of $G$ is defined similarly except that the players color the vertices according to the first-fit rule and they only decide on the order in which it is applied. The $(a,b)$-game chromatic and Grundy numbers are defined likewise except that Alice colors $a$ vertices and Bob colors $b$ vertices in each round. We study the behavior of these parameters for incomparability graphs of posets with bounded width. We conjecture a complete characterization of the pairs $(a,b)$ for which the $(a,b)$-game chromatic and Grundy numbers are bounded in terms of the width of the poset; we prove that it gives a necessary condition and provide some evidence for its sufficiency. We also show that the game chromatic number is not bounded in terms of the Grundy number, which answers a question of Havet and Zhu.

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

Recommendations

• Generalised online colouring problems in overlap graphs
• A note on online colouring problems in overlap graphs and their complements
• Online coloring co-interval graphs
• Online Bounded Coloring of Permutation and Overlap Graphs
• Automata, Languages and Programming
• Online Conflict‐Free Coloring for Intervals
• Online conflict-free coloring for intervals
• Deterministic conflict-free coloring for intervals: from offline to online
• Online vertex-coloring games in random graphs
• On-Line Coloring and Recursive Graph Theory

zbMATH Keywords

chromatic numbertriangle-freeintersection graphline segmentsGrundy numbergame chromatic numberincomparability graphs

Mathematics Subject Classification ID

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

Cites Work

• An Effective Version of Dilworth's Theorem
• First-Fit Coloring of Incomparability Graphs
• A bound for the game chromatic number of graphs
• Title not available (Why is that?)
• Game chromatic number of outerplanar graphs
• ON THE COMPLEXITY OF SOME COLORING GAMES
• 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
• Radius two trees specify χ‐bounded classes
• Asymmetric graph coloring games
• Activation strategy for asymmetric marking games

Cited In (6)

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

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

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