2010 / December Volume 5 No.4
Oriented circuit double cover and circular flow and colouring
| Published Date |
2010 / December
|
|---|---|
| Title | Oriented circuit double cover and circular flow and colouring |
| Author | |
| Keyword | |
| Download | |
| Pagination | 349-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)$. |
| AMS Subject Classification |
60F15
|
| Received |
2010-08-26
|
| Accepted |
2010-12-01
|