adv

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查看全文

Solidot 文章翻译

你的名字

留空匿名提交
你的Email或网站

用户可以联系你
标题

简单描述
内容