Annales de l’institut Fourier (AIF)

Panyushev, Dmitri I.

On spherical nilpotent orbits and beyond

Siebert, Bernd

Algebraic and symplectic Gromov-Witten invariants coincide

Blasco, Laure

Blondel, Corinne

Types induits des paraboliques maximaux de $Sp_4(F)$ et $GSp_4(F)$

Lamari, Ahcène

Courants kählériens et surfaces compactes

Buchdahl, Nicholas

On compact Kähler surfaces

Bannai, Eiichi

Modular invariance property of association schemes, type II codes over finite rings and finite abelian groups and reminiscences of François Jaeger (a survey)

Colin De Verdière, Yves

Déterminants et intégrales de Fresnel

Jackson, Bill

Whitehead, Carol A.

ANNALES DE L’INSTITUT FOURIER
BILL JACKSON
CAROL A. WHITEHEAD
Some remarks on Jaeger’s dual-hamiltonian
conjecture
Annales de l’institut Fourier, tome 49, no 3 (1999), p. 921-926
<http://www.numdam.org/item?id=AIF_1999__49_3_921_0>
© Annales de l’institut Fourier, 1999, tous droits réservés.
L’accès aux archives de la revue « Annales de l’institut Fourier »
(http://annalif.ujf-grenoble.fr/) implique l’accord avec les conditions gé-
nérales d’utilisation (http://www.numdam.org/conditions). Toute utilisa-
tion commerciale ou impression systématique est constitutive d’une in-
fraction pénale. Toute copie ou impression de ce fichier doit conte-
nir la présente mention de copyright.
Article numérisé dans le cadre du programme
Numérisation de documents anciens mathématiques
http://www.numdam.org/
Ann. Inst. Fourier, Grenoble
49, 3 (1999), 921-926
SOME REMARKS ON JAEGERS
DUAL-HAMILTONIAN CONJECTURE
by Bill JACKSON and C.A. WHITEHEAD
We consider finite simple graphs without loops or multiple edges. Let
G be a connected graph. A cocircuit of G is a minimal set of edges of G
whose removal disconnects G. Thus X is a cocircuit of G if and only if
G — X has exactly two components and every edge of X is incident with
both components. It follows that if X is a cocircuit then \X\ < \E\ — \V\-\-2^
with equality if and only if both components of G — X are trees. We shall
say that X is a Hamilton cocircuit of G if \X\ = \E\ - \V\ +2 and, following
Jaeger [3], that G is dual hamiltonian if G has a Hamilton cocircuit. These
definitions are motivated by matroid duality, from which it follows that a
plane graph is hamiltonian if and only if its dual graph is dual hamiltonian.
Thus conditions implying hamiltonicity in plane graphs can be readily
translated to conditions implying dual hamiltonicity in plane graphs. We
will be concerned with a conjecture of Jaeger [3] which suggests that one
such condition for dual hamiltonicity generalises to non-planar graphs. To
state his conjecture we need one further definition. Suppose that G contains
two edge disjoint circuits. Then G is said to be cyclically k-connected if
whenever we partition G into two subgraphs H^ and H^ both of which
contain circuits, we have \V(H-i) H V{H'z)\ > k. Thus, if G is cyclically k-
connected, then each circuit of G must have length at least k. The concept of
cyclic connectivity is the matroid dual to the 'standard5 definition of graph
connectivity, see [4]. In particular, a plane graph is /^-connected if and only
if its dual is cyclically fc-connected. It follows that the classical result of
Keywords: Cubic graphs - Hamilton circuits - Cocircuits.
Math. classification: 05C05 - 05C45.
922 BILL JACKSON & C.A. WHITEHEAD
Whitney [7] that every 4-connected plane triangulation is hamiltonian is
equivalent to:
THEOREM 1. — Every cyclically 4-connected planar cubic graph is
dual hamiltonian.
The above mentioned conjecture of Jaeger is that this result remains
valid for non-planar graphs.
CONJECTURE 1. — Every cyclically 4-connected cubic graph is dual
hamiltonian.
Using Tutte's generalization [6] of Whitney's Theorem, we may
deduce that every cyclically 4-connected planar graph is dual hamiltonian.
It is not true, however, that this more general result remains valid for non-
planar graphs. To see this, consider the graph G whose vertex set is the
union of five disjoint independent sets of size three, 61, 62, . . . , 65, in which
each vertex of Si is adjacent to every vertex of 6^4.1 for 1 <, i <, 5, where
subscripts are to be read modulo five. Then G is cyclically 4-connected since
G is 4-connected and has girth 4. Suppose G is dual hamiltonian. Then
V(G) can be partitioned into two subsets Ti.Fa, each of which induces
a tree in G. Without loss of generality we may assume |Ti D 611 ^> 2.
Then \T^ H 62] > 2, otherwise Ti H (61 U 52) will induce a 4-circuit in G.
Continuing this reasoning we eventually deduce that |Ti H 65] > 2. But
then TI H (61 U 65) will induce a 4-circuit in G.
For the remainder of this note, we shall restrict our attention to
cubic graphs. For such graphs the concept of cyclic 4-connectivity can be
simplified as follows: a cubic graph G -^ K^ is cyclically 4-connected if and
only if the only edge cuts in G with fewer than four edges are obtained
by taking three edges incident with some vertex. Jaeger's main concern
in [3] involved the parameter 5(G), which he defined to be the size of a
largest induced forest in G. He showed that, if G is a cubic graph, then
s(G) <, |_(3|y| - 2)/4J, and furthermore that if G is dual hamiltonian then
equality holds. He was led to make Conjecture 1 by the result of Payan and
Sakarovitch [5] that s(G) = [{3\V\ - 2)/4J for all cyclically 4-connected
cubic graphs G. (There are many conjectures which would imply that the
family of cyclically 4-connected cubic graphs has nicer properties than the
entire family of 3-connected cubic graphs. The above mentioned result of
Payan and Sakarovitch is the only solid evidence we know of in support of
this statement.) In the remainder of this note we shall make several remarks
JAEGER'S DUAL-HAMILTONIAN CONJECTURE 923
on Conjecture 1.
The following result shows that Conjecture 1 is equivalent to a
conjecture concerning an edge-partition of a cubic graph.
LEMMA 2. — A cubic graph G is dual hamiltonian if and only if the
edge set of G can be partitioned into two trees.
Proof. — Suppose G is dual hamiltonian. Then V(G) can be parti-
tioned into two induced trees T^,T^. Let H be the spanning subgraph of
G containing all edges which join T\ and T^. Then H is a bipartite graph
of maximum degree two and so has a two edge colouring E\, E^. Then
E(T^) U J^i, E(T^ U £'2 is the required partition of E(G) into two trees.
Suppose, on the other hand, that E(G) has a partition T[^ T^ into two
trees. Let Ti be the tree obtained from T[ by deleting all its end vertices.
Then Ti, T^ is the required partition of V(G) into two induced trees. D
It follows that Conjecture 1 is equivalent to:
CONJECTURE 2. — The edge set of every cyclically 4-connected
cubic graph G can be partitioned into two trees.
Given a cubic graph G and e € E(G), let Ge be the cubic (multi)-
graph obtained from G — e by suppressing its two vertices of degree two.
One may try to use the following lemma as a basis for an inductive proof
of Conjecture 1.
LEMMA 3. — Let G be a cubic graph and e = v^v^ be an edge of
G. Let Ci be the edge of Ge 'containing7 Vi for 1 < i < 2. Suppose Ge
has a Hamilton cocircuit containing e\. Then G has a Hamilton cocircuit
containing e.
Proof. — Let T\,T^ be a partition of V{Ge) into two induced trees
such that e\ is incident with both T\ and T^. We may suppose without loss
of generality that either 62 is also incident with both T\ and T^ or that 62
is an edge of the tree induced by T-z. In either case T\ + z^i, T^ + V2 is the
required partition of V(G). D
An obvious approach to using this lemma would be to try to use it
to prove:
924 BILL JACKSON & C.A. WHITEHEAD
CONJECTURE 3. — Let G be a cyclically 4-connected cubic graph
and e e E(G). Then G has a Hamilton cocircuit containing e.
This approach fails if Ge is not cyclically 4-connected. We have tried
to get around this problem by working with various more complicated
induction hypotheses, in line with either Conjecture 1 or 2. One such
attempt is described below.
The problem with using Lemma 3 occurs when Ge no longer belongs
to the family of graphs for which the inductive hypothesis applies. To get
round this we could try to work with a larger family than the family of
cyclically 4-connected cubic graphs. To define such a family we proceed as
follows.
Let G be a 3-connected cubic graph. Suppose that G is not cyclically
4-connected and is not isomorphic to K^. Let X be a 'non-trivial' 3-edge
cut in G and H\, H^ the two components of G — X. For 1 < i <^ 2 let Gi
be the 3-connected cubic graph obtained from G by contracting H^-i to a
new vertex v. We shall refer to v as a marker vertex in G\ and G^. We now
iterate this procedure for both G\ and G^. We continue until we obtain a
collection of cubic graphs S each of which is either cyclically 4-connected
or else is isomorphic to K^. We shall refer to these graphs as pieces of G.
Note that each 'non-trivial' 3-edge cut of G will be represented by a marker
vertex in exactly two pieces of G. We define a new graph D whose vertices
are the pieces of (7, and in which two pieces are joined by an edge if they
have a marker vertex in common. It follows from the decomposition theory
developed by Cunningham and Edmonds in [1] that D is a tree and that the
set of pieces 5' and the tree D are uniquely defined by G. We shall refer to
D as the decomposition tree of G and the pieces of G which correspond to
end-vertices of D as end-pieces of G. We believe that if G is a 3-connected
cubic graph whose decomposition tree has maximum degree at most three
then G is dual hamiltonian. The bound on the maximum degree of the
decomposition tree comes from the construction described below.
One may construct a 3-connected cubic graph H which is not dual
hamiltonian by taking any 3-connected cubic graph G on at least six
vertices and 'blowing up5 each vertex v of G into a triangle Cy. To see
this we use Lemma 2. Suppose E(H) can be partitioned into two trees
Ti, T2. Since each triangle Cy in H must contain two edges of one tree and
one edge of the other tree we see that Pi = Ti H E{G), P^ = T^ H E{G) is
a partition of E(G) into two connected spanning subgraphs of maximum
JAEGER'S DUAL-HAMILTONIAN CONJECTURE 925
degree two. This is clearly impossible since G is cubic and has more than
four vertices. If we begin with the triangular prism Go and apply this
construction recursively we obtain an infinite sequence of 3-connected cubic
graphs Go, Gi , . . . such that, for i > 1, Gi is not dual hamiltonian and has
a decomposition tree of maximum degree four. (The decomposition tree for
Go is K^. The decomposition tree for G^+i can be obtained from that of
Gi by attaching three new leaves to each of its end-vertices.)
One can try to apply Lemma 3 inductively to the family of 3-
connected cubic graphs whose decomposition tree has maximum degree
three by formulating a conjecture as follows:
CONJECTURE 4. — Let G be 3-connected cubic graph whose de-
composition tree D has maximum degree at most three and e be an edge of
G which lies in an end piece of G. Then G has a Hamilton cocircuit which
contains e.
Adopting the notation of Lemma 3, it can be seen that Ge will be a
3-connected cubic graph with a decomposition tree D of maximum degree
at most three. Furthermore, either e\ or 63 will belong to an end piece of
Ge unless the end piece Gi of G which contains e is isomorphic to K^ (that
is to say e belongs to a triangle of G), and the unique neighbour of Gi in
D has degree three. Unfortunately, if this second alternative occurs, then
both 61 and 63 will belong to a piece of Ge which has degree two in the
decomposition tree of Ge and the inductive argument again fails.
Working with Yu [2], the first named author has recently verified
Conjecture 4 for planar graphs by proving the dual statement to:
THEOREM 4. — Let G be a 3-connected planar cubic graph. Sup-
pose that G has a decomposition tree D of maximum degree at most three.
Let Gi be a piece of G corresponding to a vertex of D of degree at most
two, and e, f be edges both incident with a vertex of Gi which is not a
marker vertex. Then G has a Hamilton cocircuit through e and f.
Although this result gives some evidence in favour of Conjecture 4, its
current proof is discouraging since it makes even greater use of planarity
than Whitney's original theorem.
926 BILL JACKSON & C.A. WHITEHEAD
BIBLIOGRAPHY
[1] W.H. CUNNINGHAM and J. EDMONDS, A combinatorial decomposition theory,
Canadian J. Math., 32 (1980), 734-765.
[2] B. JACKSON and X. Yu, Hamilton cycles in plane triangulations, submitted.
[3] F. JAEGER, On vertex induced forests in cubic graphs, Proc. Fifth Southeastern
Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica,
Winnipeg (1974), 501-512.
[4] J.G. OXLEY, Matroid Theory, Oxford Univ. Press, Oxford, 1992.
[5] C. PAYAN and M. SAKAROVITCH, Ensembles cycliquement stables et graphes
cubiques, Cahiers du C.E.R.O., 17 (1975), 319-343.
[6] W. T. TUTTE, A theorem on planar graphs, Trans. Amer. Math. Soc., 82 (1956),
99-116.
[7] H. WHITNEY, A theorem on graphs, Ann. of Math., 32 (1931), 378-390.
Bill JACKSON & C.A. WHITEHEAD,
Goldsmiths College
Department of Mathematical and
Computing Sciences
London SE14 6NW (England).


Some remarks on Jaeger's dual-hamiltonian conjecture

Tarsi, Michael

ANNALES DE L’INSTITUT FOURIER
MICHAEL TARSI
The graph polynomial and the number of
proper vertex coloring
Annales de l’institut Fourier, tome 49, no 3 (1999), p. 1089-1093
<http://www.numdam.org/item?id=AIF_1999__49_3_1089_0>
© Annales de l’institut Fourier, 1999, tous droits réservés.
L’accès aux archives de la revue « Annales de l’institut Fourier »
(http://annalif.ujf-grenoble.fr/) implique l’accord avec les conditions gé-
nérales d’utilisation (http://www.numdam.org/conditions). Toute utilisa-
tion commerciale ou impression systématique est constitutive d’une in-
fraction pénale. Toute copie ou impression de ce fichier doit conte-
nir la présente mention de copyright.
Article numérisé dans le cadre du programme
Numérisation de documents anciens mathématiques
http://www.numdam.org/
Ann. Inst. Fourier, Grenoble
49, 3 (1999), 1089-1093
THE GRAPH POLYNOMIAL AND THE NUMBER
OF PROPER VERTEX COLORINGS
by Michael TARSI
1. Introduction.
Let G = (V, E) be a graph, V = { 1 , 2 , . . . , n}, let
PG= II {x,-x,)
ij^E,i<j
be its graph polynomial, and let PkG be the remainder of this polynomial
modulo the ideal generated by the polynomials x^ — 1, 1 < i < n. Put
Z^ = {0 ,1 , . . . , k - I}71. For a polynomial
n
P=P(^i,...,^)= ̂  a,]"]^1.
vez^ 1=1
Define ||P|||= ^ l^l2.
vez?
In a recent joint work with Noga Alon, [2] we proved the folowing
result, in which Cfc(G) is the set of all proper colorings c of a graph G by
the k colors { 0 , . . . , k — 1}.
THEOREM 1.1. — In the above notation
m ii^iij'̂  E n ̂ [̂ (J"].
ceCk{G)ijeE,i<j
Keywords: Graph coloring - Graph polynomial.
Math. classification: 05C35.
1090 MICHAEL TARSI
Theorem 1.1 clearly provides a lower bound for the number of proper
^-colorings of a graph G in terms of HP^HI- For the special case k = 3
this is an equality, showing that the precise number |G3(G)| of proper 3-
colorings satisfies
(2) ||P3G||i=3l£;l-n|C3(G)|.
The following notation is used in the sequel: A Partial orientation of
a graph is obtained when some edges are assigned with an orientation while
the other edges remain undirected.
Given a partial orientation and a vertex x, the number of oriented
edges with their tails, (heads) at x is denoted by d^{x}, {d~{x)).
A A;, I—flow in a graph G = (V, E) is a partial orientation of G, where
for every vertex x € V, d^~(x) — d~(x} '= 0 (mod A;).
F^(G) stands for the set of all fc, 1-flows of G.
The support a(f) of a flow / € F^(G) is the set of edges of G which
are oriented in /.
The main result of this paper is the following equality, which gives
another combinatorial interpretation to the left hand side of 1:
THEOREM 1.2.
(3) II^G||i=(-l)^ E (-2)1£;1-K/)1.
f^(G)
Note that Ff^(G) corresponds to the subset of Fk(G) (the set of all
Zk— flows in G) where the permitted flow values are 1,—1 and 0. Since
Zs = {0,1, —1}, in the special case of k = 3 we obtain
(4) II^Glli^-l)^ E (-2)l£;l-w)l
f^F^G)
and by 2
(5) 3^1-^3(^1 = (-1)^1 E (-2)1^1-1^)1.
feF3(G)
Considering the parity of the right hand side, all summands are clearly
even, except those corresponding to flows / for which a(/) = E. These flows
are the 3- Nowhere Zero Flows (3 - N Z F ) of G. This implies:
GRAPH POLYNOMIAL AND NUMBER OF PROPER VERTEX COLORINGS 1091
THEOREM 1.3. — The set of3-Nowhere zero flows (NZF^G)) and
the set of proper 3-colorings of a graph G are of the same parity, or more
precisely
(6) \Cs{G)\ = |7VZF3(^)|(mod4).
Remark. — Clearly IC^G)] is always divisible by 6 (permutations
of the 3 colors) and flows come in pairs (obtained by reversing the entire
orientation). It is a common convention, however, to refer to permutations
of the colors as the same coloring (e.g. phrases like "uniquely /c-colorable"
etc.). Accordingly, when talking of an "odd" |C3(G')| we actually refer to 2
modulo 4 and the same holds to the parity of NZF^(G).
One can easily observe that in 4-regular graphs, Eulerian orientations
are the only 3—Nowhere zero flows. The following is then a direct conse-
quence of Theorem 1.3:
THEOREM 1.4. — The set of proper 3-colorings of a 4-regular graph
G and the set of Eulerian orientations of G have the same parity.
Fleischner and Stiebitz [3] proved that in every (Cycle and triangles'
graph there is an odd number of Eulerian orientations. They used this
result and the 'Graph polynomial method' presented in [I], to prove that
such graphs are 3-colorable. Recently Sachs [4] proved, by means of direct
induction, that the number of 3-colorings of every Cycle and triangles
graph is odd. Theorem 1.4 shows that Sachs result can be derived from the
Fleischner and Stiebitz Lemma. This observation provides an affirmative
answer to a question posted by Jack Edmonds.
2. Proving the main result.
As observed in [I], each term in the expansion of PG to the sum
of 2^1 monomials, corresponds to an orientation of G. Similar terms,
that is monomials with the same degree for every variable, correspond to
orientations which share the same outdegree sequence {d^~{x)\x G V}.
When computing P^G) two monomials are similar if the correspond-
ing degrees are congruent modulo k. The outdegree sequences correspond-
ing to such two monomials are clearly, term by term, congruent modulo k.
We refer to such orientations as k— equivalent.
1092 MICHAEL TARSI
Let uj\ and 01:2 be two orientations of a graph G = (V,£1), and let
0:1 A 0:2 denote the set of edges whose orientation is reversed when going
from uj\ to uj^. For uj\ and 0^2 to be ^-equivalent, uj\ A uj^ should satisfy
(as a subgraph of any of the two orientations) d^(x) = d~(x) (mod A;) for
every x G V. In other words, uj\ A uj^ should be the support of a A:, I—flow
inG.
Furthermore, selecting either x or y as the head of an edge ( x ^ y ) ^
corresponds to the selection of either x or —y from the term (x — y)^ in the
expansion of PG (and of PkG 0s well). Two A;—equivalent orientations uj\
and c<;2 then yield similar monomials, of the same sign, if \uj\ Acj2| is even,
or of different signs, if it is odd.
Let us agree that an edge (xi^xj) with i < j is oriented backwards
if its head is at a^, and define parity (c<;) = 0 if the number of backwards
oriented edges is even and parity ((j) = 1 if this number is odd.
For v e Z^ let Sy be the A;—equivalence class of orientations of G
with d^^Xi) = Vi (mod A;), 1 ̂  i < n, and let 5^, respectively S^ denote
the subsets of even, respectively odd orientations in that class.
For any uj € Sy, let (F^)°(a;), respectively (F^)1^) be the sets
of fc, I—flows, the supports of which are even, respectively odd oriented
subgraphs of uj.
Following the discussion above we obtain
(7) a^l^l-l^l
and for i = 0,1 (0 = 1,1 = 0) and any m e S^:
(8) 1(^)^)1 = 1 |̂ and \(F^(^=\S^\.
Consider now the quantity
^ (K^1)0^)! - K^)^)!).
wCSv
By 8 it can be rewritten as:
EI^I-I^I+ EI^I-I^I-
uess ^es^
By 7, this equals:
^a,- ^a, =(|^|-|^|)a, =4
ujes° ^es1
GRAPH POLYNOMIAL AND NUMBER OF PROPER VERTEX COLORINGS 1093
Summing up the above over all equivalent classes we obtain
(9) IIPBllJ- E (K^1)0^)!-!^1)1^)!)
o/€D(G)
where D(G) is the set of all orientations of G.
Let us now change the order of summation in the right hand side of 9 by
taking fc, I—flows, instead of orientation, as the leading index:
(10) iipam = ^ (-I)W)I|D(/)|.
^^(G)
Here D{f) = {(^\f C Fj^(uj)} is the set of all expansions of / to (complete)
orientations (of all the edges) of G.
An expansion of a partial orientation is constructed by selecting an
orientation for each undirected edge and hence \D(f)\ = 2l£;l-l<T^I which
completes the proof of Theorem 1.2.
BIBLIOGRAPHY
[1] N. ALON and M. TARSI, Colorings and orientations of graphs, Combinatorica, 12
(1992), 125-134.
[2] N. ALON and M. TARSI, A note on graph colorings and graph polynomials, J.
Comb. Theory, B 70 (1997), 197-201.
[3] H. FLEISCHNER and M. STIEBITZ, A solution to a Colouring problem of P. Erdos,
Discrete Math., 101 (1992), 39-48.
[4] H. SACHS, Elementary proof of the cycle-plus-triangles theorem, in: Combinatorics,
Paul Erdos is Eighty, Janos Bolyai Math. Soc., Budapest, 1993, Vol 1, 347-359.
Michael TARSI,
Tel Aviv University
Raymond and Beverly Sackler
Faculty of Exact Sciences
School of Mathematical Sciences
Tel Aviv (Israel).
tarsi@math.tau.ac.il


The graph polynomial and the number of proper vertex coloring

Hansson, Thomas

On Hardy spaces in complex ellipsoids

Not a member yet