# Integer flows and cycle covers of graphs

### Cun-Quan `C. Q.' Zhang

#### New York, NY 10016

Click here for CONTENTS of the book.:

Click here for ERRATA of the book.:

Please send suggestion and comments to C. Q. Zhang

# UPDATE

About Conjecture 1.1.5 (5-Flow Conjecture) on page 4, and Chapter 5.

Martin Kochol recently proved [MK] that
if the 5-flow conjecture is not true, then the determination of whether a bridgeless graph admitting a nowhere-zero 5-flow is an NP-complete problem.

Reference.
[MK] Martin Kochol, Hypothetical complexity of 5 flow problem, (preprint, 1996).

About Conjecture 1.1.7 (Edge-3-Coloring Conjecture) on page 5, and Chapter 3.

K. Kilakos and B. Shepherd have obtained a partial result to the Edge-3-Coloring Conjecture [KS1996]. They proved that
Let $G$ be a cubic bridgeless graph. If $G$ does not contain $P_{10} - {e}$ (where $e$ is an edge of the Petersen graph $P_{10}$) as a minor, then $G$ edge-3-colorable.
The 4-Color Theorem is applied in their proof.

References.
[KS1996] K. Kilakos and B. Shepherd, Excluding Minors in Cubic Graphs, Combinatorics, Probability and Computing, 5, (1996) p. 57-78.

On page 82, about Theorem 3.9.3 and Conjecture 1.1.7.

It was announced by D. Sanders [ST] at a workshop in May 1997:
Sanders and Thomas have proved that every apex is edge-3-colorable. The proof uses the techniques (computer-assisted proof) employed in the proof of the four-color theorem [RSST 1997].
Now the doublecross is the only remaining case for Conjecture 1.1.7 (see Theorem 3.9.3).

References.
[RSST 1997] N. Robertson, D. Sanders, P. D. Seymour and R. Thomas, The 4-color theorem. JCTB, Vol. 70, No. 1, (1997) p2-44.
[ST] D. Sanders, Edge-3-coloring cubic apex graphs, Abstract of a presentation at the Workshop on Graph Colouring and Applications, May 5-9 1997, Centre de recherches mathematiques, Universite de Montreal, Canada.

On page 91.

The following is a counterexample to Conjecture 3.11.7:
Let G be obtained from the Petersen graph by replacing one vertex by a triangle. There is a 1-factor M using no edge of the triangle, and if you contract M you get the octahedron (planar). Yet G is not 3-edge-colourable. (Pointed out by Paul Seymour 2/13/1997).

On page 107.

Problem 4.6.2 was solved by Abbott and Zhou ([Abbott1991]) for $i : 4 \leq i \leq 11$ and improved by Sanders and Zhao ([Sanders1995}]) for $i : 4 \leq i \leq 9$.

References.
[Abbott 1991] H. L. Abbott and B. Zhou, On small faces in 4-critical planar graphs, Ars Combin. 32, (1991) p. 203-207.
[Sanders 1995] D. P. Sanders and Y. Zhao, A note on the three color problem, 11, Graph and Combinatorics, (1995) p. 91-94.

About 5-flow Conjecture and Theorem 5.1.5 on page 111.

In the paper [SE], the 5-flow conjecture (Conjecture 1.1.5) is proved for all graphs of order at most 43 and all graphs with nonorientable genus at most 5. (This improves Theorem 5.1.5.)

References.
[SE] E. Steffen, Tutte's 5-Flow Conjecture for Graphs of nonorientable Genus 5, J. of Graph Theory 22, 309-319 (1996).

On page 150, Conjecture 6.10.2:

Pointed out by Romeo Rizzi (personal communication with Bill Jackson) that Conjecture 6.10.2 is false. The following is a counterexample: take the Petersen graph and give a 1-factor with weight 2k and all other edges with weight k for any odd k.

Reference.
Personal communication with B. Jackson, 8/1997

On Page 179 and page 210.

Conjecture 8.1.13 is recently solved by G. Fan [Fan]

References.
[Fan] G. - H. Fan, Proofs of two minimum circuit cover conjectures, JCTB 74 (1998) p.353-367

On page 262

Some recent results in [Kouider 1996] and [Heinrich 1996] are related to Problem 10.7.5.

References
[Heinrich 1996] K. Heinrich, J.-P. Liu and C. Q. Zhang, Triangle-free circuit decompositions and Petersen-minor, JCTB (to appear)
[Kouider 1996] M. Kouider and G. Sabidussi, Factorizations of $4$-regular graphs and Petersen's Theorem, JCT B 63(1995), 170-184

On page 279

Conjecture 11.6.1 (the unique edge-3-coloring conjecture by Fiorini and Wilson) is solved by T. Fowler and R. Thomas. The following is a part of the abstract of their announcement at a workshop in May 1997.
We give a computer-assisted proof of the conjecture. More precisely, using the techniques employed in the proof of the four-color theorem [RSST 1997] we prove ... that every "internally 6-connected" planar triangulation has at least two (vertex) 4 colorings. ... ...

References.
[RSST 1997] N. Robertson, D. Sanders, P. D. Seymour and R. Thomas, The 4-color theorem. JCTB, Vol. 70, No. 1, (1997) p2-44.
[FT] T. Fowler, Characterizing uniquely 4-colorable planar graphs, Abstract of a presentation at the Workshop on Graph Colouring and Applications, May 5-9 1997, Centre de recherches mathematiques, Universite de Montreal, Canada.

On page 280.

The following result is proved in [Lai 1996] which is related to Conjectures 11.6.6 and 11.6.7:
Let $G$ be a 3-connected cubic graph containing no Petersen-minor. It $G$ admits a Hamilton weight then $G$ contains a triangle.

References.
[Lai 1996] H. J. Lai and C. Q. Zhang, Hamilton weights and Petersen minors, (preprint) (1996).

On page 280, Problem 11.6.10

R. Rizzi constructed a family of 4-connected eulerian graphs that do not have even circuit decompositions [Rizzi].
May we consider the same problem for 5-connected or 5-edge-connected eulerian graphs?

Reference:
[Rizzi] Romeo Rizzi, On 3-connected graphs without even cycle decompositions. preprint (1999)

Please send suggestion and comments to C. Q. Zhang

Back to the homepage of C. Q. Zhang
Back to the contents of the book.