<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 3" %>
The Interleaved Multichromatic Number of a Graph
Valmir C. Barbosa
Universidade Federal do Rio de Janeiro, Programa de Engenharia de Sistemas e COPPE, Caixa Postal 68511, 21941-972 Rio de Janeiro - RJ, Brazil
Annals of Combinatorics 6 (3) p.249-256 September, 2002
AMS Subject Classification: 05C15
For k≡1, we consider interleaved k-tuple colorings of the nodes of a graph, that is, assignments of k distinct natural numbers to each node in such a way that nodes that are connected by an edge receive numbers that are strictly alternating between them with respect to the relation <. If it takes at least distinct numbers to provide graph G with such a coloring, then the interleaved multichromatic number of G is and is known to be given by a function of the simple cycles of G under acyclic orientations if G is connected [1]. This paper contains a new proof of this result. Unlike the original proof, the new proof makes no assumptions on the connectedness of G, nor does it resort to the possible applications of interleaved k-tuple colorings and their properties.
Keywords: chromatic number, multichromatic number, interleaved multichromatic number, acyclic orientations


1. V.C. Barbosa and E. Gafni, Concurrency in heavily loaded neighborhood-constrained systems, ACM Trans. Program. Lang. Systems 11 (1989) 562每584.

2. F.H. Clarke and R.E. Jamison, Multicolorings, measures and games on graphs, Discrete Math. 14 (1976) 241每245.

3. R.W. Deming, Acyclic orientations of a graph and chromatic and independence numbers, J. Combin. Theory, Ser. B 26 (1979) 101每110.

4. D. Geller and S. Stahl, The chromatic number and other functions of the lexicographic product, J. Combin. Theory, Ser. B 19 (1975) 87每95.

5. S. Stahl, n-tuple colorings and associated graphs, J. Combin. Theory, Ser. B 20 (1976) 185每 203.