Open Problem Garden

Importance: Medium ✭✭

Author(s):

Subject:	Graph Theory
	» Basic Graph Theory
	» » Connectivity

Keywords:	edge-coloring
	edge-connectivity

Recomm. for undergrads: no

Prize: bottle of wine (DeVos)

Posted	by:	mdevos
	on:	March 7th, 2007

Question Let $G$ be an $(a+b+2)$ -edge-connected graph. Does there exist a partition $\{A,B\}$ of $E(G)$ so that $(V,A)$ is $a$ -edge-connected and $(V,B)$ is $b$ -edge-connected?

By the Nash-Williams/Tutte theorem ([NW] or [T]) on disjoint spanning trees, the above conjecture is true if $G$ is $2(a+b)$ -edge-connected. This is the only partial result I know of. Here is a related conjecture.

Conjecture There exists a fixed integer $k$ so that every $k$ -edge-connected graph $G=(V,E)$ has a subset of edges $S$ with the property that every edge-cut of $G$ has between $\frac{1}{3}$ and $\frac{2}{3}$ of its edges in $S$ .

The values $\frac{1}{3}$ and $\frac{2}{3}$ are of no special importance in the above conjecture. Indeed, an affirmative answer to the above problem with $\frac{1}{3}$ and $\frac{2}{3}$ replaced by $\frac{1}{t}$ and $1 - \frac{1}{t}$ for any $t > 0$ would still be valuable - and in particular, would imply the 2+epsilon flow conjecture.

Definition: Let $G=(V,E)$ be a graph and let $P=\{E_1,E_2,...,E_t\}$ be a partition of $E$ . We say that $P$ is $k$ -courteous if $G \setminus E_i$ is $k$ -edge-connected for every $1 \le i \le t$ .

Problem What is the smallest integer $t$ so that every 3-edge-connected graph has a 2-courteous coloring of size $t$ ?

It is known (see [DJS]) that $4 \le t \le 10$ . It would be quite interesting if the truth were in fact $t=4$ . An improvement on the current upper bound would have some consequences for certain flow problems and cycle-cover problems. In general, one may define a function $H : {\mathbb Z}^2 \rightarrow {\mathbb Z} \cup \{\infty\}$ so that $H(a,b)$ is the smallest integer $t$ (or $\infty$ if none exists) so that every $a$ -edge-connected graph has a $b$ -courteous coloring of size $t$ . It is known (see [DJS]) that $H(2k+2,2k+1) = \infty$ , and that $2k+1 < H(2k+1,2k) < C 100^k$ . Two special cases when better values are known are $2 < H(4,2) < 5$ and $5 < H(5,4) < 31$ .