On a heterochromatic number for hypercubes (Q932668): Difference between revisions

The heterochromatic number \(h_c(H)\) of a non-empty hypergraph \(H\) is the smallest integer \(k\) such that for every colouring of the vertices of \(H\) with \(k\) colours, there is a hyperedge of \(H\) all of whose vertices have different colours. The authors study the heterochromatic number of a class of hypergraphs obtained in the following way: Let \(G\) be a graph and \(H_G\) be the hypergraph with vertex set \(V(H_G)=V(G)\) in which a set \(A\) of vertices forms a hyperedge if and only if \(A\) is the set of neighbours of some vertex of \(G\). The neighbourhood heterochromatic number \(nh_c(G)\) of a nonempty graph \(G\) is the smallest integer \(\ell\) such that for every colouring of \(G\) with exactly \(\ell\) colours, \(G\) contains a vertex all of whose neighbours have different colours. Let \(G^n\) denote the \(n\)th product of a connected graph \(G\) with at least two vertices. Then \(\lim_{n\to\infty}(nh_c(G^n)-1)/|V(G^n)|=1\). Lower and upper bounds for the heterochromatic number of the \(2^n\)-dimensional hypergraph are given.