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