solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看13129次
Fractional coloring with local demands. (arXiv:1811.11806v1 [math.CO])
来源于:arXiv
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 查看全文>>