(k,lambda)-colorings and universal graphs

We consider vertex k-colorings of an arbitrary simple, connected, and undirected graph G=(V,E) such that, for every vertex v, at most lambda different colors occur in the closed neighborhood of v. These colorings are called (k,lambda)-colorings. If a graph has a (k,lambda)-coloring with lambda < chi we say that the graph is oligomatic. We present some results concerning universal graphs U(k,lambda) which are generic (in a sense to be defined) (k,lambda)-colorable graphs. We determine the chromatic number chi of all U(k,lambda) with k=<10 and we show that the graph U(2n+1,n+1) is critical with n>=2. We also show that there is no claw-free graph admitting a (chi+1, chi-1)-coloring, that there is no line graph admitting a (k,chi-2)-coloring and that there is no oligomatic Halin graph.


  • There is no available fulltext. Please contact the lab or the authors.

Related material