Graphs with tiny vector chromatic numbers and huge chromatic numbers
Michael Langberg

Abstract:

Karger, Motwani and Sudan (JACM 1998) introduced the notion of a vector coloring of a graph. In particular they show that every $k$-colorable graph is also vector $k$-colorable, and that for constant $k$, graphs that are vector $k$-colorable can be colored by roughly $\Delta^{1 - 2/k}$ colors. Here $\Delta$ is the maximum degree in the graph. Their results play a major role in the best approximation algorithms for coloring and for maximal independent set.

Karger, Motwani and Sudan (JACM 1998) introduced the notion of a vector coloring of a graph. In particular they show that every $k$-colorable graph is also vector $k$-colorable, and that for constant $k$, graphs that are vector $k$-colorable can be colored by roughly $\Delta^{1 - 2/k}$ colors. Here $\Delta$ is the maximum degree in the graph. Their results play a major role in the best approximation algorithms for coloring and for maximal independent set.

Karger, Motwani and Sudan (JACM 1998) introduced the notion of a vector coloring of a graph. In particular they show that every $k$-colorable graph is also vector $k$-colorable, and that for constant $k$, graphs that are vector $k$-colorable can be colored by roughly $\Delta^{1 - 2/k}$ colors. Here $\Delta$ is the maximum degree in the graph. Their results play a major role in the best approximation algorithms for coloring and for maximal independent set.

Joint work with U. Feige and G. Schechtman.

Host: R. Ravi