The interleaved multichromatic number of a graph

Details The interleaved multichromatic number of a graph The interleaved multichromatic number of a graph

2003-09-23

arxiv.org/abs/math/0309380v1

Annals of Combinatorics 6 (2002), 249-256

Mathematics

Combinatorics

Scientific paper

For $k\ge 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 $\chi_{int}^k(G)$ distinct numbers to provide graph $G$ with such a coloring, then the interleaved multichromatic number of $G$ is $\chi_{int}^*(G)=\inf_{k\ge 1}\chi_{int}^k(G)/k$ 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.

Affiliated with

Also associated with

No associations

Rating

The interleaved multichromatic number of a graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The interleaved multichromatic number of a graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The interleaved multichromatic number of a graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-182888