nowhere-zero flow, edge-colorings, regular graphs


Circular flow number of regular class 1 graphs ★★

Author(s): Steffen

A nowhere-zero $r$-flow $(D(G),\phi)$ on $G$ is an orientation $D$ of $G$ together with a function $\phi$ from the edge set of $G$ into the real numbers such that $1 \leq |\phi(e)| \leq r-1$, for all $e \in E(G)$, and $\sum_{e \in E^+(v)}\phi(e) = \sum_{e \in E^-(v)}\phi(e), \textrm{ for all } v \in V(G)$. The circular flow number of $G$ is inf$\{ r | G$ has a nowhere-zero $r$-flow $\}$, and it is denoted by $F_c(G)$.

A graph with maximum vertex degree $k$ is a class 1 graph if its edge chromatic number is $k$.

\begin{conjecture} Let $t \geq 1$ be an integer and $G$ a $(2t+1)$-regular graph. If $G$ is a class 1 graph, then $F_c(G) \leq 2 + \frac{2}{t}$. \end{conjecture}

Keywords: nowhere-zero flow, edge-colorings, regular graphs

Syndicate content