Publication

(k,lambda)-colorings and universal graphs

Ivo Blöchliger
2006
Reports

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

https://infoscience.epfl.ch/entities/publication/3dcb826a-538a-4121-a6f4-7e9a5b2a2182

About this result

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.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Ivo Blöchliger
2006
Reports

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/3dcb826a-538a-4121-a6f4-7e9a5b2a2182

About this result

Related concepts (31)

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.

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Edge coloring

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors.

Related publications (2)

(k,lambda)-colorings and universal graphs

Chat with Graph Search

Robust Routing for Dynamic Wireless Networks Based on Stable Embeddings

On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs