Oriented circuit double cover and circular flow and colouring
by
Zhishi Pan
Xuding Zhu
Vol. 5 No. 4 (2010) P.349~P.368
ABSTRACT
For a set ${\cal C}$ of
directed circuits of a graph $G$ that form an oriented circuit
double cover, we denote by $I_{\cal C}$ the graph with vertex set
${\cal C}$, in which two circuits $C$ and $ C'$ are connected by $k$
edges if $|\underline{C} \cap \underline{C'}| =k$. Let
$\Phi^*_c(G)={\rm min}\chi_c(I_{\cal C})$, where the minimum is
taken over all the oriented circuit double covers of $G$. It is easy
to show that for any graph $G$, $\Phi_c(G) \leq \Phi^*_c(G)$. On the
other hand, it follows from well-known results that for any integer
$2 \leq k \leq 4$, $\Phi^*_c(G) \leq k$ if and only if $\Phi_c(G)
\leq k$; for any integer $k \geq 1$, $\Phi^*_c(G) \leq 2 +
\frac{1}{k}$ if and only if $\Phi_c(G) \leq 2 + \frac{1}{k}$.
This papers proves that for any rational number $2 \leq r \leq 5$ there
exists a graph $G$ for which $\Phi^*_c(G) = \Phi_c(G) =r$. We also
show that there are graphs $G$ for which $\Phi_c(G) < \Phi^*_c(G)$.
KEYWORDS
Circuit double cover, circular flow number, edge rooted graph, flow, graph, parallel join, series join
MATHEMATICAL SUBJECT CLASSIFICATION 2010
Primary: 60F15
MILESTONES
Received: 2010-08-26
Revised :
Accepted: 2010-12-01
Download Full Content