University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Graphs and Matroids- Tom KellyExport this event to calendar

Wednesday, January 30, 2019 — 3:30 PM EST

Title: Fractional coloring with local demands

Speaker: Tom Kelly
Affiliation: University of Waterloo
Room: MC 6486

Abstract: In a fractional coloring, vertices of a graph are assigned subsets of the $[0, 1]$-interval such that adjacent vertices receive disjoint subsets. The fractional chromatic number of a graph is at most $k$ if it admits a fractional coloring in which the amount of ``color'' assigned to each vertex is at least $1/k$.  We investigate fractional colorings where vertices ``demand'' different amounts of color, determined by local parameters such as the degree of a vertex.  Many well-known results concerning the fractional chromatic number and independence number have natural generalizations in this new paradigm.  We discuss several such results as well as open problems.  In particular, we will sketch a proof of a ``local demands'' version of Brooks' Theorem that considerably generalizes the Caro-Wei Theorem and implies new bounds on the independence number.  Joint work with Luke Postle.

Location 
MC - Mathematics & Computer Building
6486
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
  1. 2020 (76)
    1. August (9)
    2. July (17)
    3. June (11)
    4. May (6)
    5. March (11)
    6. February (11)
    7. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)