A $b$-fold coloring of a graph G is an assignment of sets of size $b$ to vertices of a graph such that adjacent vertices receive disjoint sets. An $a:b$-coloring is a $b$-fold coloring out of $a$ available colors. The $b$-fold chromatic number ${\displaystyle \chi _{b}(G)}$ is the least $a$ such that an $a:b$-coloring exists.

The fractional chromatic number ${\displaystyle \chi _{f}(G)}$ is defined to be

${\displaystyle \chi _{f}(G)=\lim _{b\to \infty }{\frac {\chi _{b}(G)}{b}}=\inf _{b}{\frac {\chi _{b}(G)}{b}}}$.

The fractional edge chromatic number $\chi'_{f}(G)$ of a graph $G$ is the fractional analog of the edge chromatic number. It can be defined as $\chi'_f(G)=\chi_f(L(G))$, where $L(G)$ is the line graph of $G$.

Similarly, we can define $a:b$-edge-coloring for graphs $G$. Now I am interseted whether there are existed results on $a:2$-edge-coloring. I just want to fix $b$ to be 2 and consider corresponding questions.

Thanks in advance!


1 Answer 1


The $(a:2)$-edge-coloring problem is equivalent to replacing each edge by two parallel edges. As there are many results on edge-coloring that take the multiplicity $\mu$ into account, they naturally give results on $(a:2)$-edge-coloring (or $(a:b)$-edge-coloring, more generally).

(You have to be careful about the fact that when you double every edge, you also multiply the maximum degree by two).

For instance, here is a result that you can obtain using this observation:

Steffen (2000): Every simple graph $G$ with finite girth (=size of a smallest cycle) $g$ and maximum degree $\Delta$ has an $(a:2)$-edge-coloring with $a\le 2\Delta+1+1/\lceil g/2\rceil$

E. Steffen, A refinement of Vizing's theorem, Discrete Math. 218 (2000), 289-291.

I should add that there are hard problems related to $(a:2)$-edge coloring. The Berge-Fulkerson conjecture states that every cubic bridgeless graph has a (6:2)-edge-coloring. The conjecture was generalized by Seymour to 𝑟-graphs. Little is known about this, unfortunately.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.