Steffen, Eckhard

Circular flow numbers of $r$-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)$ .

A $(2t+1)$ -regular graph $G$ is a $(2t+1)$ -graph if $|\partial_G(X)| \geq 2t+1$ for every $X \subseteq V(G)$ with $|X|$ odd.

Conjecture Let $t > 1$ be an integer. If $G$ is a $(2t+1)$ -graph, then $F_c(G) \leq 2 + \frac{2}{t}$ .

Keywords: flow conjectures; nowhere-zero flows

Posted by Eckhard Steffen
updated August 6th, 2015

add new comment

Graph Theory » Coloring » Nowhere-zero flows

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$ .

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}$ .

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

Posted by Eckhard Steffen
updated August 5th, 2015

add new comment