**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# (k,lambda)-colorings and universal graphs

Abstract

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==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.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (2)

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.