𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the equality of the grundy and ochromatic numbers of a graph

✍ Scribed by P. Erdös; W. R. Hare; S. T. Hedetniemi; R. Laskar

Publisher
John Wiley and Sons
Year
1987
Tongue
English
Weight
162 KB
Volume
11
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

It is proved in this note that the Grundy number, r(G), and the ochromatic number, xo(G), are the same for any graph G.

An n-coloring of a graph G = ( V , E ) is a f u n c t i o n f f r o m V onto N = { I , 2 , . . . , n } such that, whenever vertices id and u are adjacent, then f ( u ) f f(u). An n-coloring is complete i f for every pair i, j of integers, 1 5 i 5 j 5 n , there exist a pair u , u of adjacent vertices such that f ( u ) = i andf(u) = j . The chromatic number, x ( G ) , and the achromatic number, $(G), are the smallest and largest values n , respectively. for which G has a complete n-coloring. A complete n-coloring g : V -+ N is a Grundy n-coloring if, for every vertex u E V , g(u) is the smallest integer that is not assigned to any vertex adjacent to u. The Grundy number, T(G), is the largest IZ for which G has a Grundy n-coloring.

📜 SIMILAR VOLUMES

On the geodetic number of a graph
On the geodetic number of a graph
✍ Gary Chartrand; Frank Harary; Ping Zhang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB
On the Interval Number of a Triangulated
On the Interval Number of a Triangulated Graph
✍ Thomas Andreae 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 414 KB 👁 2 views

The interval number of a simple undirected graph G, denoted i(G), is the least nonnegative integer r for which we can assign to each vertex in G a collection of at most r intervals on the real line such that two distinct vertices u and w of G are adjacent if and only if some interval for u intersect

On the interval number of a chordal grap
On the interval number of a chordal graph
✍ Edward R. Scheinerman 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB 👁 2 views

The interval number of a (simple, undirected) graph G is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t real intervals. A chordal (or triangulated) graph is one with no induced cycles on 4 or more vertices. If G is chordal and has maximum

Graphs on the Torus and Geometry of Numb
Graphs on the Torus and Geometry of Numbers
✍ A. Schrijver 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 424 KB

We show that if \(G\) is a graph embedded on the torus \(S\) and each nonnullhomotopic closed curve on \(S\) intersects \(G\) at least \(r\) times, then \(G\) contains at least \(\left\lfloor\frac{3}{4} r\right\rfloor\) pairwise disjoint nonnullhomotopic circuits. The factor \(\frac{3}{4}\) is best

On the chromatic number of disk graphs
On the chromatic number of disk graphs
✍ Malesi?ska, Ewa; Piskorz, Steffen; Wei�enfels, Gerhard 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB 👁 2 views

Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their