Bipartite weighted coloring

本文考虑了bipartite weighted edge coloring problem, 将带权二部图$G$的两个顶点之间的重边根据权重进行合并得到辅助图$G’$，然后用Konig Theorem给$G’$染色，导出了$G$的一个边染色，从而给出了$G$所用颜色数的一个上界$\min(\lfloor \frac{7n}{4}+\frac{5r}{8}+\frac{15}{8}\rfloor,\lfloor \frac{7n}{4}+\frac{r+1}{2}+\frac{1}{4}\min(n,r)\rfloor )$, 其中$n$为图中用来pack与任意一个顶点关联的边所需要的最少的bins的个数.

本文考虑了bipartite weighted edge coloring problem, 将带权二部图$G$根据权重进行边分解，结合Konig Theorem给出了所用颜色数的一个上界$\lceil \frac{17n-5}{16}\rceil$, 其中$n$为图中与一个顶点相关联的边的权和的最大值。

本文用bin packing的方法考虑了bipartite weighted edge coloring problem, 给出了所用颜色数的一个上界$2.557n + o(n)$, 其中$n$为图中与一个顶点相关联的边的权和的最大值。