✦ LIBER ✦

Game coloring the Cartesian product of graphs

✍ Scribed by Xuding Zhu

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 186 KB
Volume: 59
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20338

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

This article proves the following result: Let G and G′ be graphs of orders n and n′, respectively. Let G^*^ be obtained from G by adding to each vertex a set of n′ degree 1 neighbors. If G^*^ has game coloring number m and G′ has acyclic chromatic number k, then the Cartesian product G□G′ has game chromatic number at most k(k + m − 1). As a consequence, the Cartesian product of two forests has game chromatic number at most 10, and the Cartesian product of two planar graphs has game chromatic number at most 105. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 261–278, 2008

📜 SIMILAR VOLUMES

The Game Coloring Number of Planar Graph

The Game Coloring Number of Planar Graphs

✍ Xuding Zhu 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 121 KB

This paper discusses a variation of the game chromatic number of a graph: the game coloring number. This parameter provides an upper bound for the game chromatic number of a graph. We show that the game coloring number of a planar graph is at most 19. This implies that the game chromatic number of a

s-strongly perfect cartesian product of

s-strongly perfect cartesian product of graphs

✍ Elefterie Olaru; Eugen Mǎndrescu 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB

## Abstract The study of perfectness, via the strong perfect graph conjecture, has given rise to numerous investigations concerning the structure of many particular classes of perfect graphs. In “Perfect Product Graphs” (__Discrete Mathematics__, Vol. 20, 1977, pp. 177‐‐186), G. Ravindra and K. R.

On super connectivity of Cartesian produ

On super connectivity of Cartesian product graphs

✍ Min Lü; Chao Wu; Guo-Liang Chen; Cheng Lv 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 176 KB

On super edge-connectivity of Cartesian

On super edge-connectivity of Cartesian product graphs

✍ Min Lü; Guo-Liang Chen; Jun-Ming Xu 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB

Embedding Cartesian Products of Graphs i

Embedding Cartesian Products of Graphs into de Bruijn Graphs

✍ Thomas Andreae; Michael Nölle; Gerald Schreiber 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 172 KB

## Given a Cartesian product G of nontrivial connected graphs G i and the n-dimensional base B de Bruijn graph D = D B (n), it is investigated whether or not G is a spanning subgraph of D. Special attention is given to graphs G 1 × • • • × G m which are relevant for parallel computing, namely, to

Cartesian Products of Graphs and Metric

Cartesian Products of Graphs and Metric Spaces

✍ S. Avgustinovich; D. Fon-Der-Flaass 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 68 KB

We prove uniqueness of decomposition of a finite metric space into a product of metric spaces for a wide class of product operations. In particular, this gives the positive answer to the long-standing question of S. Ulam: 'If U × U V × V with U , V compact metric spaces, will then U and V be isometr