(1997) ISBN: 0-8247-9790-6
270 Madison Ave.
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.