𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Coloring graph products — A survey

✍ Scribed by Sandi Klavẑar

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
564 KB
Volume
155
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

There are four standard products of graphs: the direct product, the Cartesian product, the strong product and the lexicographic product. The chromatic number turned out to be an interesting parameter on all these products, except on the Cartesian one. A survey is given on the results concerning the chromatic number of the three relevant products. Some applications of product colorings are also included.

📜 SIMILAR VOLUMES

An edge coloring problem for graph produ
An edge coloring problem for graph products
✍ Faudree, R. J.; Gy�rf�s, Andr�as; Schelp, R. H. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 315 KB 👁 1 views

The edges of the Cartesian product of graphs G x H a r e to be colored with the condition that all rectangles, i.e., K2 x K2 subgraphs, must be colored with four distinct colors. The minimum number of colors in such colorings is determined for all pairs of graphs except when G is 5-chromatic and H

Asymmetric graph coloring games
Asymmetric graph coloring games
✍ H. A. Kierstead 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB

## Abstract We introduce the (__a,b__)‐coloring game, an asymmetric version of the coloring game played by two players Alice and Bob on a finite graph, which differs from the standard version in that, in each turn, Alice colors __a__ vertices and Bob colors __b__ vertices. We also introduce a relat

A Simple Competitive Graph Coloring Algo
A Simple Competitive Graph Coloring Algorithm
✍ H.A. Kierstead 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 157 KB

We prove that the game coloring number, and therefore the game chromatic number, of a planar graph is at most 18. This is a slight improvement of the current upper bound of 19. Perhaps more importantly, we bound the game coloring number of a graph G in terms of a new parameter r(G). We use this resu

Coloring the square of a planar graph
Coloring the square of a planar graph
✍ Jan van den Heuvel; Sean McGuinness 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

## Abstract We prove that for any planar graph __G__ with maximum degree Δ, it holds that the chromatic number of the square of __G__ satisfies χ(__G__^2^) ≤ 2Δ + 25. We generalize this result to integer labelings of planar graphs involving constraints on distances one and two in the graph. © 2002

Coloring a graph optimally with two colo
Coloring a graph optimally with two colors
✍ H.J. Broersma; F. Göbel 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 536 KB

Let G be a graph with point set V. A (2.)c,oloring of G is a map of V to ired, white!. An error occurs whenever the two endpoints of a line have the same color. An oprimul doring of G is a coloring of G for which the number of errors is minimum. The minimum number of errors is denoted by y(G), we de