Fractional coloring with local demands. (arXiv:1811.11806v1 [math.CO])
We investigate fractional colorings of graphs in which the amount of color
given to a vertex depends on local parameters, such as its degree or the clique
number of its neighborhood; in a \textit{fractional $f$-coloring}, vertices are
given color from the $[0, 1]$-interval and each vertex $v$ receives at least
$f(v)$ color. By Linear Programming Duality, all of the problems we study have
an equivalent formulation as a problem concerning weighted independence
numbers. However, these problems are most natural in the framework of
fractional coloring, and the concept of coloring is crucial to most of our
proofs.
Our results and conjectures considerably generalize many well-known
fractional coloring results, such as the fractional relaxation of Reed's
Conjecture, Brooks' Theorem, and Vizing's Theorem. Our results also imply
previously unknown bounds on the independence number of graphs. We prove that
if $G$ is a graph and $f(v) \leq 1/(d(v) + 1/2)$ for each $v\in V(G)$, then
either $G$ has查看全文