Reed's well-known $\omega$, $\Delta$, $\chi$ conjecture proposes that every graph satisfies $\chi \leq \lceil \frac 12(\Delta+1+\omega)\rceil$. The second author formulated a local strengthening of this conjecture that considers a bound supplied by the neighbourhood of a single vertex. Following the idea that the chromatic number cannot be greatly affected by any particular stable set of vertices, we propose a further strengthening that considers a bound supplied by the neighbourhoods of two adjacent vertices. We provide some fundamental evidence in support, namely that the stronger bound holds in the fractional relaxation and holds for both quasi-line graphs and graphs with stability number two. We also conjecture that in the fractional version, we can push the locality even further.
@article{10_37236_2666,
author = {Katherine Edwards and Andrew D. King},
title = {A superlocal version of {Reed's} conjecture},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {4},
doi = {10.37236/2666},
zbl = {1305.05074},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2666/}
}
TY - JOUR
AU - Katherine Edwards
AU - Andrew D. King
TI - A superlocal version of Reed's conjecture
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/2666/
DO - 10.37236/2666
ID - 10_37236_2666
ER -
%0 Journal Article
%A Katherine Edwards
%A Andrew D. King
%T A superlocal version of Reed's conjecture
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/2666/
%R 10.37236/2666
%F 10_37236_2666
Katherine Edwards; Andrew D. King. A superlocal version of Reed's conjecture. The electronic journal of combinatorics, Tome 21 (2014) no. 4. doi: 10.37236/2666
