✦ LIBER ✦

Playing a Game to Bound the Chromatic Number

✍ Scribed by Panagiota N. Panagopoulou, Paul G. Spirakis

Book ID: 115528008
Publisher: Mathematical Association of America
Year: 2012
Tongue: English
Weight: 227 KB
Volume: 119
Category: Article
ISSN: 0002-9890
DOI: 10.4169/amer.math.monthly.119.09.771

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A bound for the game chromatic number of

A bound for the game chromatic number of graphs

✍ Thomas Dinski; Xuding Zhu 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 580 KB

We show that if a graph has acyclic chromatic number k, then its game chromatic number is at most k(k + 1). By applying the known upper bounds for the acyclic chromatic numbers of various classes of graphs, we obtain upper bounds for the game chromatic number of these classes of graphs. In particula

A New Game Chromatic Number

✍ G. Chen; R.H. Schelp; W.E. Shreve 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 263 KB

Consider the following two-person game on a graph G . Players I and II move alternatively to color a yet uncolored vertex of G properly using a pre-specified set of colors . Furthermore , Player II can only use the colors that have been used , unless he is forced to use a new color to guarantee that

The incidence game chromatic number

✍ Stephan Dominique Andres 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 535 KB

A Bound on the Total Chromatic Number

✍ Michael Molloy; Bruce Reed 📂 Article 📅 1998 🏛 Springer-Verlag 🌐 English ⚖ 481 KB

Using stable sets to bound the chromatic

Using stable sets to bound the chromatic number

✍ D. de Werra; P. Hansen 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 89 KB

A generalization of the Roy-Gallai theorem is presented: it is based on the existence in any oriented graph of a stable set S such that for any node w not in S there is an elementary path from some node of S to w. The bound obtained improves earlier results by Berge and by Li.

Playing the numbers game

✍ Powell, Patricia A.; Wesley, Cedric; Spencer, Susan; Cagan, Ross L. 📂 Article 📅 2001 🏛 Nature Publishing Group 🌐 English ⚖ 478 KB