Theory Lunch Seminar

Wednesday, November 11, 2015 - 12:00pm to 1:00pm

Location:

ASA Conference Room 6115 Gates & Hillman Centers

Speaker:

JOSHUA BRAKENSIEK, Mathematical Sciences /JOSHUA%20BRAKENSIEK

Event Website:

http://www.cs.cmu.edu/~theorylunch/20151111.html

For More Information, Contact:

dwajc@cs.cmu.edu

Finding a proper coloring of a t-colorable G with t colors is a classic NP-hard problem when t >= 3. In this talk, we investigate the approximate coloring problem in which the objective is to find a proper c-coloring of G where c >= t. We show that for all t >= 3, it is NP-hard to find a c-coloring when c

Keywords:

Seminar Series