Importance: Medium ✭✭
Author(s): Steffen, Eckhard
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: Eckhard Steffen
on: August 6th, 2015

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.

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

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}

Since every $(2t+1)$-regular class 1 graph is a $(2t+1)$-graph, the truth of this conjecture would imply the truth of the conjecture on the circular flow number of regular class 1 graphs. If it is true for even $t$, say $t=2t'$, then Jaeger's modular orientation conjecture is true for $(4t'+1)$-regular graphs and hence, by a result of Jaeger, it would imply the truth of Tutte's 5-flow conjecture. For $t=2$ it is Tutte's 3-flow conjecture.


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries) *[ES_2015]E. Steffen, Edge-colorings and circular flow numbers on regular graphs, J. Graph Theory 79, 1–7, 2015

* indicates original appearance(s) of problem.


Comments are limited to a maximum of 1000 characters.