We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

On a local version of Reed's conjecture

Formal Metadata

Title
On a local version of Reed's conjecture
Title of Series
Number of Parts
24
Author
Contributors
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
In 1998, Reed conjectured that the chromatic number of a graph is at most the average of its maximum degree plus one and its clique number (rounded up). As evidence for his conjecture, he proved that it is at most some non-trivial convex combination of the two. Recently, Michelle Delcourt and I proved the same is true for list chromatic number. Tom Kelly and I meanwhile conjectured that a `local' version of Reed's conjecture wherein the parameters are replaced by local parameters (list size, degree and clique number of neighborhood) and proved a non-trivial convex combination under some mild assumptions.
Keywords