Abstracts of papers by D. R. Woodall
(latest at end)
D. R. Woodall,
The λ–μ problem,
J. London Math. Soc. (2) 1 (1969), 509–519.
-
It is shown that, if S is a family of proper subsets of a set
of v elements such that every μ-set of elements is contained
in exactly λ of the subsets, then the number of subsets in S
is not less than the value of
λ(vCμ)/(kCμ)
when k is the larger root of
(k−μ+2)(k−μ+1) = λ(v−μ+1).
The cases of equality, and the possibility of improving the bound,
are discussed.
D. R. Woodall,
A market problem,
J. Combin. Theory Ser. B 10 (1971), 275–287.
-
The problem described in the introduction is solved in its complete generality.
Some general formulae are deduced concerning non-increasing sequences of
n integers between 0 and n inclusive.
The connections with the combinatorial marriage problem are discussed.
D. R. Woodall,
Square λ-linked designs,
Proc. London Math. Soc. (3) 20 (1970), 669–687.
-
A λ-linked design is an abstract system of v 'points' and
b 'lines' such that every two points are joined by exactly
λ lines.
A partial classification is given of those extremal examples with
b = v, and necessary and sufficient conditions
are given for them to be of each of the only two non-trivial types
known, namely square BIBDs and point-complemented square BIBDs.
For each λ > 1 the number of examples not of the
first type is finite.
A partial classification is also given of λ-linked designs
with one more line than points, in which every point has the same
number of lines.
Finally, if the points and lines of a λ-linked design are divided
into v′ and b′ classes respectively, and the
number of points of any class on a line depends only on the class of the
line, then b′ ≥ v′, and if
b′ = v′ the division is a tactical
decomposition.
D. R. Woodall,
Thrackles and deadlock, in D. J. A. Welsh, ed.,
Combinatorial Mathematics and its Applications,
Proc. 1969 Oxford Combinatorial Conference
(Academic Press, London and New York, 1971), 335–347.
-
Assuming the truth of the thrackle conjecture (which is not proved)
a complete classification is given of finite thrackleable graphs.
A complete classification is also given of straight thrackles, not
assuming the conjecture, and another special class of thrackles is discussed.
D. R. Woodall,
Distances realized by sets covering the plane,
J. Combin. Theory Ser. A 14 (1973), 187–200.
-
A proof is given of the (known) result that, if real n-dimensional
Euclidean space Rn is covered by any
n + 1 sets, then at least one of these sets is such
that each distance d (0 < d < ∞)
is realized as the distance between two points of the set.
In particular, this result holds if the plane is covered by three sets;
but it does not necessarily hold if the plane is covered by six sets.
If each set in a covering of the plane fails to realize the same
distance d, say d = 1, and if the sets are
either closed or simultaneously divisible into regions (in a sense
to be made precise), then at least six sets are needed and seven suffice,
and the number of closed sets needed is at least as great as the number
simultaneously divisible into regions.
[See also the following paper, which explains how to correct a mistake
in the proof:
S. P. Townsend,
Every 5-coloured map in the plane contains a monochrome unit,
J. Combin. Theory Ser. A 30 (1981), 114–115.]
D. R. Woodall,
Sufficient conditions for circuits in graphs,
Proc. London Math. Soc. (3) 24 (1972), 739–755.
-
Certain lower bounds on the valencies of the vertices in a graph,
and/or on the total number of edges, suffice to ensure the existence
in the graph of a circuit of at least, or exactly, a certain specified length.
Many theorems of this type are listed, some old and some new.
The culminating result on undirected graphs shows how many edges are needed
in a graph on n vertices, with minimal valency at least k,
in order to ensure the existence of a circuit of length exactly
n−r.
(Erdös mentioned the case k = 0,
as an unsolved problem, in 1969: see [5].)
A few of these results have been extended to directed graphs.
The main extension proved here is that if G is a directed graph on
n vertices, in which
ρout(a)+ρin(b) ≥ n
for every pair of distinct vertices a and b such that
a is not joined to b (by an edge of G), then G
has a (directed) Hamiltonian circuit.
T. H. Jackson, J. H. Williamson and D. R. Woodall,
Difference-covers that are not k-sum-covers I,
Proc. Camb. Phil. Soc. 72 (1972), 425–438.
-
Various constructions are described for sets
F = F(q,k,l) of residues
module q such that F−F contains all residues
while (k)F = F+F+...+F
(k summands) omits l consective residues, in the cases
F = 2, 3, 4 and 5.
Let Q(k,l) denote the set of moduli q
for which such a set F(q,k,l) exists.
The following results are proved:
q ∈ Q(2,1) if and only if
q ≥ 6;
q ∈ Q(2,l)
if q ≥ 4l+2;
29, 31 and 33 ∈ Q(3,1), and
q ∈ Q(3,1) if q ≥ 35;
24l+21 ∈ Q(3,l), and
q ∈ Q(3,l) if
q ≥ 44l+41.
Upper bounds are also obtained for the least elements in
Q(4,l) and Q(5,l).
D. R. Woodall,
The Bay Restaurant—a linear storage problem,
Amer. Math. Monthly 81 (1974), 240–246.
-
Suppose
l ≥ l2 ≥ l1 > 0.
Suppose that, at random times, items whose lengths are between
l1 and l2 are inserted into and
withdrawn from a linear store, subject to the restrictions that at
no moment do we wish to store items whose total length exceeds l,
and that items may not be moved within the store between their insertion
and their withdrawal.
The minimum length of store necessary for this to be possible is at least
¼l(log2(l2/l1)−4)
and at most
l(log2(l2/l1)+3).
It is one of the more surprising features of this theory that both of
these bounds tend to infinity as l1 → 0.
D. R. Woodall,
The binding number of a graph and its Anderson number,
J. Combin. Theory Ser. B 15 (1973), 225–255.
-
The binding number of a graph G, bind(G), is defined;
some examples of its calculation are given, and some upper bounds for it
are proved. It is then proved that, if bind(G) ≥ c,
then G contains at least |G|c/(c+1) disjoint
edges if 0 ≤ c ≤ ½, at least
|G|(3c−2)/3c − 2(c−1)/c
disjoint edges if 1 ≤ c ≤ 4/3,
a Hamiltonian circuit if c ≥ 3/2,
and a circuit of length at least 3(|G|−1)(c−1)/c if
1 < c ≤ 3/2 and G is not one of
two specified exceptional graphs. Each of these results is best possible.
-
The Anderson number of a graph is defined.
The Anderson numbers of a few very simple graphs are determined;
and some rather weak bounds are obtained, and some conjectures made,
on the Anderson numbers of graphs in general.
D. R. Woodall,
Property B and the four-colour problem, in
D. J. A. Welsh and D. R. Woodall, eds,
Combinatorics, Proc. 1972 Oxford Combinatorial Conference
(Institute of Mathematics and its Applications, Southend-on-Sea, 1972),
322–340.
-
The four-colour conjecture is equivalent to the conjecture that the
family of odd circuits of a loopless planar graph (when regarded as
sets of edges) has property B.
This connection between property B and the four-colour problem is
discussed, and some sufficient conditions for property B are exhibited.
For example, if a family F of sets has the property that,
for each set S, the number of sets of F contained in
S is at most |S| − 1, then F has
property B. (The rôle of the four-colour problem in this
investigation is primarily one of motivation for the results about
property B; no new results are obtained on the four-colour problem itself.)
D. R. Woodall,
Two results on infinite transversals, in
D. J. A. Welsh and D. R. Woodall, eds,
Combinatorics, Proc. 1972 Oxford Combinatorial Conference
(Institute of Mathematics and its Applications, Southend-on-Sea, 1972),
341–350.
-
Two necessary and sufficient conditions are proved for the existence
of a transversal of a family of sets consisting of an infinite number
of finite sets and a finite number of infinite sets.
The conditions are fairly natural extensions of the conditions of Rado
and Jung for the case in which there is only one infinite set.
They are basically similar to, and are proved equivalent to, the
condition of Brualdi and Scrimger, but they are simpler, and one is
more 'Hall-like' in character.
The methods of proof are 'elementary' throughout.
D. R. Woodall,
The induction of matroids by graphs,
J. London Math. Soc. (2) 10 (1975), 27–35.
-
It is known [1, 4, 5, 10] that,
if M is a matroid defined on the set of vertices
of a graph G, then the sets of vertices of G that are linked
onto independent sets in M by disjoint paths in G form the
independent sets of another matroid, the matroid induced by
G from M.
A short proof of this is given here, followed by some generalizations
of it with other types of linking.
(See the examples at the beginning of section 4.)
It is proved in passing that if X and Y are sets of vertices
in a graph G, then
X can be linked onto Y by edge-disjoint paths at most m
of which pass through any vertex, if and only if
X can be linked onto Y by edge-disjoint paths that can be
divided up into m sets in such
a way that each two paths in the same set are actually vertex-disjoint.
The paper concludes with a result on gammoids.
D. R. Woodall,
An exchange theorem for bases of matroids,
J. Combin. Theory Ser. B 16 (1974), 227–228.
-
Theorem. Given two bases B1 and B2 of a
matroid (M,r), and a partition
B1 = X1∪Y1,
there is a partition
B2 = X2∪Y2
such that X1∪Y2 and
X2∪Y1 are both bases of M.
D. R. Woodall,
A note on rank functions and integer programming,
Discrete Math. 17 (1977), 215–218.
-
An attempt is made, with only partial success, to obtain integer analogues
of some linear-programming results that are useful in combinatorics.
D. R. Woodall,
A sufficient condition for Hamiltonian circuits,
J. Combin. Theory Ser. B 25 (1978), 184–186.
-
A theorem is proved that is (in a sense) the best possible improvement
on the following theme: If G is an undirected graph on n
vertices in which
|Γ(S)| ≥ ⅓(n+|S|+3)
for every non-empty subset S of the vertices of G,
then G is Hamiltonian.
D. R. Woodall,
Circuits containing specified edges,
J. Combin. Theory Ser. B 22 (1977), 274–278.
-
Given any l (≥ 2) disjoint edges in a
(2l−2)-connected graph, there is a circuit containing all of them.
D. R. Woodall,
Menger and König systems, in
Y. Alavi and D. R. Lick, eds,
Theory and Applications of Graphs,
Lecture Notes in Mathematics 642
(Springer-Verlag, Berlin, Heidelberg and New York, 1978), 620–635.
-
A system of sets is called a Menger system or a König system
if it has properties that were originally proved to hold for certain special
systems by Menger and by König, respectively, in the theorems that
customarily bear their names.
In this survey paper, these properties are specified, and
the relationship between them is described. Some known theorems about them
are stated. Some systems of sets of edges of graphs with these properties
are exhibited. The main (and very substantial) omission from this survey is
any mention of rational analogues of these properties and the connection
with polyhedra and linear programming, for which see, for example,
[2–5, 10, 16, 17] and references cited therein.
D. R. Woodall,
A theorem on cubes,
Mathematika 24 (1977), 60–62.
-
It is proved that, if R is a set of r vertices of an
n-dimensional cube, then the number of distinct mid-points of
line-segments joining pairs of points of R (including the points
of R themselves as mid-points) is at least rα,
where α = log 3/log 2.
This result is (in a sense) best possible.
D. R. Woodall,
Zeros of chromatic polynomials, in P. J. Cameron, ed.,
Combinatorial Surveys,
Proc. Sixth British Combinatorial Conference
(Academic Press, London and New York, 1977), 199–223.
-
This paper provides an introduction to the theory of chromatic polynomials
of graphs, especially of plane triangulations.
The emphasis is on the location of real zeros, especially on inequalities
that prove the existence of zero-free regions, and on the multiplicities
of the integer zeros.
For example, it is proved that the chromatic polynomial of a plane
triangulation does not have a zero in the range
2.5 ≤ t < 2.546602... .
The paper finishes with two interesting infinite families of examples.
B. Bollobás, D. L. Goldsmith and D. R. Woodall,
Indestructive deletions of edges from graphs,
J. Combin. Theory Ser. B 30 (1981), 263–275.
-
If G is a graph on p vertices with connectivity, or edge-connectivity,
or minimum valency, at least k, we ask how many edges one can delete
from G without reducing the appropriate quantity below
k−1.
When p and k are large, our answers are about
¼p, ⅛p, and ½p, respectively;
we conjecture that the correct (best possible) answer is about
½p in each case.
D. R. Woodall,
Dividing a cake fairly,
J. Math. Anal. Appl. 78 (1980), 233–247.
-
If each of n people defines a (suitable) measure on a compact convex
cake I, then there exists a division of I into n
connected parts, and an assignment of these n parts to the n
people, in such a way that the piece of cake assigned to each person is
at least as large (in his own measure) as that assigned to anyone else.
(The proof uses Brouwer's fixed-point theorem and Hall's theorem on systems
of distinct representatives.)
Slight progress is made towards finding algorithms for this problem.
D. R. Woodall,
Some notes on Feinberg's k-independence problem,
J. Combin. Theory Ser. B 32 (1982), 350–352.
-
A short proof is given of a recent theorem of M. Feinberg on
representable matroids.
The result is shown not to hold for nonrepresentable matroids
of rank 3.
D. R. Woodall,
Vector transversals,
J. Combin. Theory Ser. B 32 (1982), 189–205.
-
The max-flow min-cut theorem is used to give a necessary and sufficient
condition for one or two finite families of finite non-negative vectors
to have a (common) vector transversal.
The duality theorem of linear programming is then used to prove the
polymatroid intersection theorem for any finite number of polymatroids,
which in turn is used to give a necessary and sufficient condition for
any finite number of families of finite sets to have a common vector
transversal.
(This result was announced without proof in [D. R. Woodall, in
"Combinatorics (Proceedings, 4th British Combinatorial Conference)"
pp, 195–200, London Mathematical Society Lecture Note Series No. 13,
Cambridge Univ. Press, London/New York 1974].)
This provides a weak generalization of the well-known conditions of
Hall and of Ford and Fulkerson for one and two families of sets,
respectively, to have a (common) transversal.
It also provides a stronger necessary condition than was previously
known for three or more families of sets to have a common transversal.
W. E. Opencomb,
On the intricacy of combinatorial construction problems,
Discrete Math. 50 (1984), 71–97.
-
A combinatorial research week was held at the Open University from 20–23
September 1982, at which D. E. Daykin described how he and
R. Häggkvist had conceived a concept of 'intricacy', and posed the
problem [5] of showing that the intricacy of latin squares is two.
This inspired the participants to develop the concept and apply it to
a variety of combinatorial problems, both during the week and in collaboration
thereafter.
-
The original latin square problem remains in precisely the same state of
partial solution as was achieved by Daykin and Häggkvist;
but the concept which it generated seems to be of enough interest to be
worthy of exposition.
-
The name W. E. Opencomb is a flag of convenience under which Open
University combinatorial weeks aspire to sail.
The participants on this occasion were:
R. A. Bailey,
P. J. Cameron,
A. G. Chetwynd,
D. E. Daykin,
A. J. W. Hilton,
F. C. Holroyd,
J. H. Mason,
R. Nelson,
C. A. Rowley and
D. R. Woodall.
W. Stromquist and D. R. Woodall,
Sets on which several measures agree,
J. Math. Anal. Appl. 108 (1985), 241–248.
-
It is known that, given n non-atomic probability measures
on the space I = [0,1], and a number α between 0 and 1,
there exists a subset K of I that has measure α
in each measure.
It is proved here that K may be chosen to be a union of at most
n intervals.
If the underlying space is the circle S1 instead of I,
then K may be chosen to be a union of at most n−1 intervals.
These results are shown to be best possible for all irrational and many
rational values of α.
However, there remain many rational values of α for which we are
unable to determine the minimum number of intervals that will suffice.
J. G. Kingston, C. Rogers and D. R. Woodall,
Reciprocal auto-Bäcklund transformations,
J. Phys. A: Math. Gen. 17 (1984), L35–L38.
-
Invariant Bäcklund transformations of reciprocal type are derived
for a class of (n+1)th-order conservation laws.
A new auto-Bäcklund transformation for the Harry-Dym equation is
presented as a special case of the analysis.
L. J. Cowen, R. H. Cowen and D. R. Woodall,
Defective colorings of graphs in surfaces:
partitions into subgraphs of bounded valency,
J. Graph Theory 10 (1986), 187–195.
-
We call a graph (m,k)-colorable if its vertices can be colored
with m colors in such a way that each vertex is adjacent to at most
k vertices of the same color as itself.
For the class of planar graphs, and the class of outerplanar graphs,
we determine all pairs (m,k) such that every graph in the class
is (m,k)-colorable.
We include an elementary proof (not assuming the truth of the four-color
theorem) that every planar graph is (4,1)-colorable.
Finally, we prove that, for each compact surface S, there is an integer
k = k(S) such that every graph in S
can be (4,k)-colored;
we conjecture that 4 can be replaced by 3 in this statement.
D. R. Woodall,
Subcontraction-equivalence and Hadwiger's conjecture,
J. Graph Theory 11 (1987), 197–204.
-
The concept of subcontraction-equivalence is defined, and 14 graph-theoretic
properties are exhibited that are all subcontraction-equivalent if Hadwiger's
conjecture is true.
Some subsets of these properties are proved to be subcontraction-equivalent
anyway.
Hadwiger's conjecture is expressed as the union of three independent and
strictly weaker subconjectures.
As a first step toward one of these subconjectures, it is proved that
a graph that does not have Km+1 as a subcontraction
must contain an independent set consisting of at least
½(m−1) of its vertices.
D. R. Woodall,
An impossibility theorem for electoral systems,
Discrete Math. 66 (1987), 209–211.
-
An impossibility theorem is proved for electoral systems that has
something of the flavour of Arrow's General Possibility Theorem [1],
but is logically unrelated to it.
The implications for the Single Transferable Vote are discussed.
P. Katerinis and D. R. Woodall,
Binding numbers of graphs and the existence of k-factors,
Quart. J. Math. (2) 38 (1987), 221–228.
-
We prove that, if k ≥ 2 is an integer and G
is a graph with p ≥ 4k−6 vertices and
binding number b(G) such that kp is even and
b(G) > (2k−1)(p−1)/[k(p−2)+3],
then G has a k-factor.
This lower bound on b(G) is best possible for all values
of p and k such that (p+4)/(4k−2) is an
integer.
Also, if p > k ≥ 2 and kp
is even and
b(G) ≥ (p−1)/2(√kp−k),
then again G has a k-factor, and this bound on
b(G) is roughly best possible if
p < 4k.
D. R. Woodall,
k-factors and neighbourhoods of independent sets in graphs,
J. London Math. Soc. (2) 41 (1990), 385–392.
-
Sufficient conditions are proved for the existence of a k-factor
or a Hamiltonian circuit in a graph G.
The main element of each condition is a statement to the effect that
|N(X)| ≥ a|X|+b|V(G)|+c
for every non-empty independent subset X of V(G).
The theorems are shown to contain various known results.
D. R. Woodall,
A proof of McKee's Eulerian-bipartite characterization,
Discrete Math. 84 (1990), 217–220.
-
A proof is given of the result about binary matroids that implies that
a connected graph is Eulerian if and only if every edge lies in an odd
number of circuits, and a graph is bipartite if and only if every edge
lies in an odd number of cocircuits (minimal cutsets).
A proof is also given of the result that the edge set of every graph
can be expressed as a disjoint union of circuits and cocircuits.
No matroid theory is assumed.
D. R. Woodall,
Forbidden graphs for degree and neighbourhood conditions,
Discrete Math. 75 (1989), 387–404.
-
For various graph-theoretic properties P that impose upper bounds
on the minimum degree or the size of a neighbourhood set, we characterize
the class G(P⊂) (G(P<))
of graphs G such that G and all its subgraphs (subcontractions)
have property P.
For example, if P is "δ ≤ xn"
(δ = minimum degree, n = number of vertices,
0 < x < 1) then
G(P⊂) = G⊂(Kr+1),
the class of graphs that do not have Kr+1
as a subgraph, where r = ⌊1/(1−x)⌋.
I. Rinsma, C. H. C. Little and D. R. Woodall,
Maximal matchings in graphs with large neighbourhoods of independent vertices,
J. Graph Theory 14 (1990), 167–171.
-
We obtain lower bounds on the size of a maximum matching in a graph
satisfying the condition
|N(X)| ≥ s
for every independent set X of m vertices,
thus generalizing results of Faudree, Gould, Jacobson, and Schelp
for the case m = 2.
D. R. Woodall,
Local and global proportionality,
Discrete Math. 102 (1992), 315–328.
-
The problem considered here is that posed by Fishburn, Hwang and Lee
concerning the proportion of elements of one colour in a 2-coloured ring.
It is required to deduce global information about this proportion from
rather restricted local information.
The problem is more or less solved for simple rings, some bounds are
obtained in general, and conjectures are made concerning both the original
problem and its generalizations to different sorts of graph.
D. R. Woodall,
Cycle lengths and circuit matroids of graphs,
Discrete Math. 105 (1992), 269–273.
-
Let G and H be graphs without cut-edges.
It is proved that there is a length-preserving group-isomorphism
between the (integer) cycle groups of G and H if and only if
G and H have isomorphic circuit matroids.
It follows that a knowledge of the length function on the cycle group of
G (up to isomorphism) conveys exactly the same amount of information
about G as does a knowledge of its circuit matroid.
This partially answers a question of O. Pretzel.
D. R. Woodall,
A short proof of a theorem of Dirac's about Hadwiger's conjecture,
J. Graph Theory 16 (1992), 79–80.
-
A short proof is given of the theorem that every graph that does not have
K4 as a subcontraction is properly vertex 3-colorable.
D. R. Woodall,
Generalizations of Hadwiger's Conjecture,
Ars Combin. 32 (1991), 289–292.
-
Conjectured generalizations of Hadwiger's Conjecture are discussed.
Among other results, it is proved that if X is a set of 1, 2 or 3
vertices in a graph G that does not have K6
as a subcontraction, then G has an induced subgraph that is
2-, 3- or 4-colourable, respectively, and contains X and at least
a quarter, a third or a half, respectively, of the remaining vertices
of G.
These fractions are best possible.
D. R. Woodall,
An inequality for chromatic polynomials,
Discrete Math. 101 (1992), 327–331.
-
It is proved that if P(G,t) is the chromatic polynomial
of a simple graph G with n vertices, m edges,
c components and b blocks, and if t ≤ 1, then
|P(G,t)| ≥ |tc(t−1)b|(1 + γs + γs2 + … + γsμ−1 + sμ),
where
γ = m − n + c,
μ = n − c − b
and
s = 1 − t.
Equality holds for several classes of graphs with few circuits.
D. R. Woodall,
A zero-free interval for chromatic polynomials,
Discrete Math. 101 (1992), 333–341.
-
It is proved that, for a wide class of near-triangulations of the plane,
the chromatic polynomial has no zeros between 2 and 2.5.
Together with a previously known result, this shows that the zero of the
chromatic polynomial of the octahedron at 2.546602... is the smallest
non-integer real zero of any chromatic polynomial of a plane triangulation.
[See also the erratum following.]
-
D. R. Woodall,
Erratum to "A zero-free interval for chromatic polynomials"
[Discrete Mathematics 101 (1992) 333–341],
Discrete Math. 275 (2004), 385–390.
-
It is claimed by the author
[Discrete Math. 101 (1992), 333–341]
that, for a wide class of near-triangulations of the plane,
the chromatic polynomial has no zeros between 2 and 2.5.
Together with previously known results, this shows that the
zero of the chromatic polynomial of the octahedron at 2.546602...
is the smallest noninteger real zero of any chromatic polynomial
of a plane triangulation.
This note corrects a mistake in the proof.
D. R. Woodall,
Cyclic-order graphs and Zarankiewicz's crossing-number conjecture,
J. Graph Theory 17 (1993), 657–671.
-
Zarankiewicz's conjecture, that the crossing number of the complete-bipartite
graph Km,n is
[½m][½(m−1)][½n][½(n−1)],
was proved by Kleitman when min(m,n)≤6,
but was unsettled in all other cases.
The cyclic-order graph COn arises naturally in the study of this
conjecture; it is a vertex-transitive harmonic diametrical (even) graph.
In this paper the properties of cyclic-order graphs are investigated and used
as the basis for computer programs that have verified Zarankiewicz's conjecture
for K7,7 and K7,9;
thus the smallest unsettled cases are now K7,11 and
K9,9.
C. D. Wakelin and D. R. Woodall,
Chromatic polynomials, polygon trees, and outerplanar graphs,
J. Graph Theory 16 (1992), 459–466.
-
It is proved that all classes of polygon trees are characterized by their
chromatic polynomials, and a characterization is given of those polynominals
that are chromatic polynomials of outerplanar graphs.
The first result yields an alternative proof that outerplanar graphs are
recognizable from their vertex-deleted subgraphs.
M. A. Seoud and D. R. Woodall,
Primary graphs,
Ars Combin. 38 (1994), 299–308.
-
Primal graphs and primary graphs are defined and compared.
All primary stars, paths, circuits, wheels, theta graphs, caterpillars
and echinoids are found, as are all primary graphs of the form
K2,n with n ≤ 927.
D. E. Manolopoulos, D. R. Woodall and P. W. Fowler,
Electronic stability of fullerenes:
eigenvalue theorems for leapfrog carbon clusters,
J. Chem. Soc. Faraday Trans. 88 (1992), 2427–2435.
-
A leapfrog carbon cluster can be constructed geometrically by omnicapping
and dualising a polyhedral parent cluster with one third the number of
carbon atoms.
In this paper the Hückel molecular orbital energy levels of leapfrog
fullerenes, and other related leapfrog carbon clusters, are investigated
analytically using graph theory.
It is proved in particular that all trivalent leapfrog clusters have
antibonding lowest unoccupied molecular orbitals (LUMOs), and that all
trivalent leapfrog clusters containing at least one ring of
r ≠ 3k atoms have bonding highest occupied
molecular orbitals (HOMOs).
More generally, all trivalent leapfrog clusters have bonding or non-bonding
HOMOs.
A chemically significant corollary is that all trivalent leapfrog clusters,
irespective of their ring counts, are closed shell.
J. D. Lamb, G. M. Asher and D. R. Woodall,
Causal loops and Mason's rule for bond graphs, in
J. J. Granada and F. E. Cellier, eds,
Internat. Conf. on Bond Graph Modeling (ICBGM '93),
Society for Computer Simulation, Simulation Series
25(2) (1993), 67–72.
-
This paper defines coenergy loops and causal loops.
It classifies causal loops as either proper or improper.
Mason's determinant rule for bond graphs is derived,
and the Mason gain formula for bond graphs is stated.
Some further results that make these two easier to apply are derived.
It is conjectured that we can write a version of Mason's determinant
rule that does not involve improper causal loops.
J. D. Lamb, D. R. Woodall and G. M. Asher,
Singular bond graphs, in
J. J. Granada and F. E. Cellier, eds,
Internat. Conf. on Bond Graph Modeling (ICBGM '93),
Society for Computer Simulation, Simulation Series
25(2) (1993), 73–78.
-
In this paper two different definitions of singularity are given,
which turn out to be equivalent.
It is shown that every bond graph is precausally equivalent to a
nonsingular bond graph.
Two different algorithms are provided for contructing nonsingular
bond graphs from a general bond graph.
Nonsingular bond graphs are shown to be important because in any
nonsingular causal assignment of a nonsingular bond graph the outputs
can be written in terms of the inputs.
For a nonsingular bond graph and a choice of inputs and outputs the
outputs can be written in terms of the inputs if and only if there is
a nonsingular causal assignment with that choice of inputs and outputs.
J. D. Lamb, D. R. Woodall and G. M. Asher,
Equivalences of bond graph junction structures, in
J. J. Granada and F. E. Cellier, eds,
Internat. Conf. on Bond Graph Modeling (ICBGM '93),
Society for Computer Simulation, Simulation Series
25(2) (1993), 79–84.
-
This paper defines precausal equivalence.
A number of precausal equivalence operations (PEOs) are described,
many of which are already familiar.
Fifteen of these PEOs are designated basic equivalence operations (BEOs).
We have shown that if two bond graphs are precausally equivalent
then one can be obtained from the other by means of the BEOs.
Thus the fifteen BEOs are sufficient to find all possible PEOs.
J. D. Lamb, G. M. Asher and D. R. Woodall,
Network realisation of bond graphs, in
J. J. Granada and F. E. Cellier, eds,
Internat. Conf. on Bond Graph Modeling (ICBGM '93),
Society for Computer Simulation, Simulation Series
25(2) (1993), 85–90.
-
This paper defines bond graphs and electrical networks to be primitive
if they contain neither transformers nor gyrators.
A bond graph is said to be primitively realisable if it is equivalent to
a primitive electrical network.
The problem of odd loops is examined.
An algorithm is described that allows us to test any bond graph for
primitive realisability.
A method for constructing primitive electrical networks is presented.
Some comments are made on the more general problem of realisability
with transformers and gyrators.
J. D. Lamb, D. R. Woodall and G. M. Asher,
Bond graphs I: acausal equivalence,
Discrete Applied Math. 72 (1997), 261–293.
-
This paper and its successor(s) aim to derive a mathematical description
of bond graphs in general and of their junction structures in particular.
It also introduces bond graphs to mathematicians that have no previous
knowledge of them.
In this introductory paper, a definition of bond graphs is given and the
concept of acausal equivalence is introduced.
Fifteen basic operations are defined and proved to be acausal equivalence
operations.
It is proved that these basic operations form a complete set, in the sense
that, if two bond graphs are acausally equivalent, then each can be converted
into the other by a sequence of these operations and their inverses.
In the course of the proof it is shown that every bond graph is acausally
equivalent to one in a standard form.
These standard bond graphs are used to demonstrate various mathematical
properties of bond graphs, and to derive a new procedure for testing whether
or not a given set of input variables uniquely determines the
corresponding set of output variables.
This should be of interest to mathematicians and engineers alike.
J. D. Lamb, D. R. Woodall and G. M. Asher,
Bond graphs II: causality and singularity,
Discrete Applied Math. 73 (1997), 143–173.
-
The concepts of causality and singularity for bond graphs are defined,
and related through the idea of a singular (or nonsingular) causal assignment,
which is one with zero (or nonzero) discriminant.
Necessary and sufficient conditions are given for a bond graph to have a
causal assignment.
It is proved that every acausal bond graph is acausally equivalent to a
nonsingular bond graph, and that every nonsingular acausal bond graph has
at least one nonsingular causal assignment for each consistent choice of
input variables.
The strong components of a causal bond graph B are defined,
and it is shown that the discriminant of B is the product of the
discriminants of its strong components; in particular, a causal assignment
is singular if and only if there is at least one singular strong component.
The reduced bond graph R(B) of B is defined and,
if B is nonsingular, R(B) is proved to be acausally
equivalent to B.
Mason's determinant rule and the Mason gain formula are proved, and a
simpler way of calculating the discriminant is derived.
D. R. Woodall,
An identity involving 3-regular graphs,
Discrete Math. 152 (1996), 287–293.
-
It is proved that, if M is a perfect matching in a 3-regular graph
G, then the number of positive-minus-negative M-covers of
G is equal to the number of positive-minus-negative M-partitions
of G.
Moreover, either there are no M-partitions of G,
or every M-partition and every M-cover has the same sign.
A. N. Walker and D. R. Woodall,
Parity sequences of triangulated polygons,
Bull. Inst. Combin. Appl. 11 (1994), 45–48.
-
Suppose one draws a polygon in the plane and labels each vertex 0 or 1.
Can one triangulate its interior in such a way that any new vertex added
has even degree, and each vertex of the polygon has even or odd degree
according as its label is 0 or 1?
We give a necessary and sufficient condition for this to be possible.
The solution involves a result on switching that may be of independent interest.
J. D. Lamb, D. R. Woodall and G. M. Asher,
Bond graphs III: bond graphs and electrical networks,
Discrete Applied Math. 73 (1997), 211–250.
-
Electrical networks are defined and a definition of when a bond graph
and an electrical network are equivalent is given.
Bond graphs and electrical networks are defined to be primitive if they
contain no transformers or gyrators.
A bond graph is defined to be realisable if it is equivalent to an electrical
network and primitively realisable if it is equivalent to a primitive
electrical network.
It is shown how to construct a bond graph equivalent to a given electrical
network and how to construct an electrical network equivalent to a given bond
graph.
Chordless odd loops are defined and a characterisation of primitively
realisable bond graphs in terms of chordless odd loops and forbidden
induced subgraphs is given.
It is shown how to construct a primitive network equivalent to a given
primitively realisable bond graph.
O. V. Borodin and D. R. Woodall,
Thirteen colouring numbers for outerplane graphs,
Bull. Inst. Combin. Appl. 14 (1995), 87–100.
-
We review thirteen colouring problems for plane and outerplane graphs,
of which several are new.
The main new results are to determine the colouring numbers
χef and χvef for all outerplane graphs
with maximum degree Δ ≥ 6,
χf/v for those with Δ ≥ 7, and
χv/f, χe/f, χve/f and
χe/vf for all outerplane graphs.
D. R. Woodall,
The largest real zero of the chromatic polynomial,
Discrete Math. 172 (1997), 141–153.
-
It is proved that if every subcontraction of a graph G contains a
vertex with degree at most k, then the chromatic polynomial of G
is positive throughout the interval (k,∞);
Kk+1 shows that this interval is the largest possible.
It is conjectured that the largest real zero of the chromatic polynomial of a
χ-chromatic planar graph is always less than χ.
For χ = 2 and 3, constructions are given for maximal
maximally-connected χ-chromatic planar graphs (i.e., 3-connected
quadrangulations for χ = 2 and 4-connected triangulations for
χ = 3) whose chromatic polynomials have real zeros
arbitrarily close to (but less than) χ.
D. R. Woodall,
A note on Fisher's inequality,
J. Combin. Theory Ser. A 77 (1997), 171–176.
-
A new proof is given of the nonuniform version of Fisher's inequality,
first proved by Majumdar. The proof is "elementary", in the sense of
being purely combinatorial and not using ideas from linear algebra.
However, no nonalgebraic proof of the n-dimensional analogue
of this result (Theorem 3 herein) seems to be known.
D. R. Woodall,
Monotonicity of single-seat preferential election rules,
Discrete Applied Math. 77 (1997), 81–98.
-
Various properties of preferential election rules are described, including
nine forms of monotonicity. It is shown that Condorcet's principle is
incompatible with many of them. Some progress is made towards the task of
determining all maximal mutually compatible subsets of these properties.
To that end, a survey is given of the monotonicity properties of many known
single-seat preferential election rules, and four new rules are described,
including one that is offered as a more monotonic practical alternative
to the Alternative Vote.
O. V. Borodin and D. R. Woodall,
Colourfully panconnected subgraphs,
Congressus Numerantium 113 (1996), 19–30.
-
Let G be a k-colourable graph with
n ≥ k vertices.
A subgraph H of G is k-colourfully panconnected
in G if there is a k-colouring of G such that the
colours are sufficiently close together in H, in two different
senses (called variegated and panconnected) to be made precise.
Let sk(G) denote the smallest number
of edges in a spanning k-colourfully panconnected subgraph
H of G.
It is easy to see that
s2(G) = n − 1,
and that (assuming G is bipartite) any spanning tree will do for
H.
It is proved here that
s3(G) ≤ n + δ − 2,
where δ is the minimum degree of G, and that this result
is best possible.
It is also proved that
s4(G) ≤ n + δ − 2.
However, it is conjectured that if k ≥ 4 then
sk(G) ≤ n.
O. V. Borodin, A. V. Kostochka and D. R. Woodall,
Total colorings of planar graphs with large maximum degree,
J. Graph Theory 26 (1997), 53–59.
-
It is proved that a planar graph with maximum degree Δ ≥ 11
has total (vertex-edge) chromatic number Δ + 1.
O. V. Borodin, A. V. Kostochka and D. R. Woodall,
List edge and list total colourings of multigraphs,
J. Combin. Theory Ser. B 71 (1997), 184–204.
-
This paper exploits the remarkable new method of Galvin (J. Combin. Theory
Ser. B 63 (1995), 153–158), who proved that the list edge
chromatic number χ'list(G) of a bipartite multigraph
G equals its edge chromatic number χ'(G). It is now
proved here that if every edge e = uw of a bipartite
multigraph G is assigned a list of at least
max{d(u),d(w)} colours, then G can be
edge-coloured with each edge receiving a colour from its list.
If every edge e = uw in an arbitrary multigraph G
is assigned a list of at least
max{d(u),d(w)} + ⌊½min{d(u),d(w)}⌋
colours, then the same holds;
in particular, if G has maximum degree
Δ = Δ(G) then
χ'list(G) ≤ ⌊3Δ/2⌋.
Sufficient conditions are given in terms of the maximum degree and maximum
average degree of G in order that
χ'list(G) = Δ and
χ''list(G) = Δ + 1.
Consequences are deduced for planar graphs in terms of their maximum degree
and girth, and it is also proved that if G is a simple planar graph
and Δ ≥ 12 then
χ'list(G) = Δ and
χ''list(G) = Δ + 1.
O. V. Borodin, A. V. Kostochka and D. R. Woodall,
Total colourings of planar graphs with large girth,
European J. Combin. 19 (1998), 19–24.
-
It is proved that if G is a planar graph with total (vertex–edge)
chromatic number χ'', maximum degree Δ and girth g, then
χ'' = Δ + 1
if Δ ≥ 5 and g ≥ 5,
or Δ ≥ 4 and g ≥ 6,
or Δ ≥ 3 and g ≥ 10.
These results hold also for graphs in the projective plane, torus and
Klein bottle.
O. V. Borodin, A. V. Kostochka and D. R. Woodall,
On kernel-perfect orientations of line graphs,
Discrete Math. 191 (1998), 45–49.
-
We exploit the technique of Galvin (1995) to prove that an orientation
D of a line-graph G (of a multigraph) is kernel-perfect
if and only if every oriented odd cycle in D has a chord (or
pseudochord) and every clique has a kernel.
O. V. Borodin and D. R. Woodall,
Short cycles of low weight in normal plane maps with minimum degree 5,
Discus. Math. Graph Theory 18 (1998), 159–164.
-
In this note, precise upper bounds are determined for the
minimum degree-sum of the vertices of a 4-cycle and a 5-cycle
in a plane triangulation with minimum degree 5:
w(C4) ≤ 25
and
w(C5) ≤ 30.
These hold because a normal plane map with minimum degree 5
must contain a 4-star with
w(K1,4) ≤ 30.
These results answer a question
posed by Kotzig in 1979 and recent questions of Jendrol' and Madaras.
O. V. Borodin and D. R. Woodall,
Weight of faces in plane maps,
Mat. Zametki 64 (1998), 648–657 [in Russian];
English translation in
Math. Notes 64 (1998), 562–570.
-
Precise upper bounds are obtained for the minimum
weight of minor faces in normal plane maps
and 3-polytopes with specified maximum vertex degree.
D. Peterson and D. R. Woodall,
Edge-choosability in line-perfect multigraphs,
Discrete Math. 202 (1999), 191–199.
-
A multigraph is line-perfect if its line graph is perfect.
We prove that if every edge e of a line-perfect multigraph G
is given a list containing at least as many colors as there are edges in a
largest edge-clique containing e, then G can be edge-colored
from its lists.
This leads to several characterizations of line-perfect multigraphs in terms
of edge-choosability properties.
It also proves that these multigraphs satisfy the
list-coloring conjecture, which states that if every edge of G
is given a list of χ'(G) colors (where χ' denotes the
chromatic index) then G can be edge-colored from its lists.
Since bipartite multigraphs are line-perfect, this generalizes Galvin's
result that the conjecture holds for bipartite multigraphs.
[See also the erratum following.]
-
D. Peterson and D. R. Woodall,
Erratum to "Edge-choosability in line-perfect multigraphs"
[Discrete Mathematics 202 (1999), 191],
Discrete Math. 260 (2003), 323–326.
-
A multigraph is line-perfect if its line graph is perfect.
In (Discrete Math. 202 (1999) 191) we claimed that
if every edge e of a line-perfect multigraph G
is given a list containing at least as many colors as there are edges in a
largest edge-clique containing e, then G can be edge-colored
from its lists.
This note corrects a mistake in our proof.
D. R. Woodall,
Edge-choosability of multicircuits,
Discrete Math. 202 (1999), 271–277.
-
A multicircuit is a multigraph whose underlying simple graph is a circuit
(a connected 2-regular graph).
The List-Colouring Conjecture (LCC)
[more sensibly called the List-Edge-Colouring Conjecture (LECC)]
is that every multigraph G has edge-choosability (list chromatic index)
ch'(G) equal to its chromatic index χ'(G).
In this paper the LCC is proved first for multicircuits,
and then, building on results of Peterson and Woodall,
for any multigraph G in which every block is bipartite or
a multicircuit or has at most four vertices or has underlying simple graph
of the form K(1,1,p).
D. G. Fon-Der-Flaass, A. V. Kostochka and D. R. Woodall,
Transversals in uniform hypergraphs with property (7,2),
Discrete Math., 207 (1999), 277–284
-
Let
f(r,p,t)
(r > t ≥ 1, r ≥ 2)
be the maximum of the cardinality of a minimum
transversal over all r-uniform hypergraphs H possessing the
property that every subhypergraph of H with p edges has a
transversal of size t.
The values of f(r,p,2) for
p = 3,4,5,6
were found by Erdös, Fon-Der-Flaass, Kostochka and Tuza (1992).
We give bounds on f(r,7,2), partially
answering a question in that paper.
O. V. Borodin and D. R. Woodall,
Cyclic degrees of 3-polytopes,
Graphs Combin. 15 (1999), 267–277.
-
A precise upper bound is obtained
for the minimum cyclic vertex degree
in a 3-polytope with specified maximum face size.
This implies improvements to some known upper bounds for the cyclic
chromatic numbers of 3-polytopes.
O. V. Borodin, A. V. Kostochka and D. R. Woodall,
Acyclic colourings of planar graphs with large girth,
J. London Math. Soc. (2) 60 (1999), 344–352.
-
A proper vertex-colouring of a graph is acyclic if there are no
2-coloured cycles.
It is known that every planar graph is acyclically 5-colourable
(Borodin, 1976 and 1979), and that there are planar graphs with
acyclic chromatic number χa = 5
and girth g = 4 (Kostochka and Melnikov, 1976).
It is proved here that a planar graph satisfies
χa ≤ 4 if g ≥ 5 and
χa ≤ 3 if g ≥ 7.
A. V. Kostochka and D. R. Woodall, On the number of edges in hypergraphs
critical with respect to strong colourings,
European J. Combin. 21 (2000), 249–255.
-
A colouring of the vertices of a hypergraph G is called strong
if, for every edge A, the colours of all vertices in A are
distinct.
It corresponds to a colouring of the generated graph Γ(G)
obtained from G by replacing every edge by a clique.
We estimate the minimum number of edges possible in a k-critical
t-uniform hypergraph with a given number of vertices.
In particular we show that, for k ≥ t+2,
the problem reduces in a way to the corresponding problem for graphs.
In the case when the generated graph of the hypergraph has bounded clique
number, we give a lower bound that is valid for sufficiently large k
and is asymptotically tight in k;
this bound holds also for list strong colourings.
P. C. Fishburn and D. R. Woodall, Cycle orders,
Order 16 (1999), 149–164.
-
Let X, T and C be, respectively, a finite set with
at least three points, a set of ordered triples of distinct points from
X, and a cyclic ordering of the points in X.
Define T ⊆ C to mean that,
for every abc ∈ T,
the elements a, b, c occur in that cyclic
order in C, and let C(T) denote the set of cyclic
orderings C of X for which
T ⊆ C.
We say that T is noncyclic if C(T) is empty,
cyclic if C(T) is nonempty,
uniquely cyclic if |C(T)| = 1,
a partial cycle order if it is cyclic and
-
T = {abc :
{abc} ⊆ C for all
C ∈ C(T)},
and a total cycle order if it is a uniquely cyclic partial
cycle order.
Many years ago E. V. Huntington axiomatized total cycle orders by
independent necessary and sufficient conditions on T.
The present paper studies the more relaxed structures of cyclic T
sets and partial cycle orders.
We focus on conditions for cyclicity, a theory of cycle dimension of partial
cycle orders, and extremal problems that address combinatorial structures
of T sets.
A. M. Robertshaw and D. R. Woodall, Triangles and neighbourhoods of
independent sets in graphs,
J. Combin. Theory Ser. B 80 (2000), 122–129.
-
It is proved that a graph of order n contains a triangle if
|N(X)| > ⅓(n+|X|)
for every independent set X of vertices.
This bound is sharp.
D. R. Woodall,
List colourings of graphs, in J. W. P. Hirschfeld, ed,
Surveys in Combinatorics, 2001,
London Math. Soc. Lecture Note Series 288,
Cambridge University Press, 2001, 269–301.
-
A list colouring of a graph is a colouring in which each vertex v
receives a colour from a prescribed list L(v) of colours.
This paper about list colourings can be thought of as being divided
into two parts.
The first part, comprising Sections 1, 2 and 6, is about proper
colourings, in which adjacent vertices must receive different colours.
It is a survey of known conjectures and results with few proofs,
although Section 6 discusses several different methods of proof.
Section 1 is intended as a first introduction to the concept of list
colouring, and Section 2 discusses conjectures and results, mainly
about graphs for which ``ch = χ''.
The other part of the paper, comprising Sections 3, 4 and 5, is about
improper or defective colourings, in which a vertex is allowed to
have some neighbours with the same colour as itself, but not too many.
Although still written mainly as a survey,
this part of the paper contains a number of new proofs and new conjectures.
Section 3 is about subcontractions, and includes
conjectures broadly similar to Hadwiger's conjecture.
Section 4 is about planar and related graphs.
Section 5 is also about planar and related graphs, but this time with
additional constraints imposed on the lists.
A. V. Kostochka and D. R. Woodall,
Sparse sets in the complements of graphs with given girth,
Discrete Math. 233 (2001), 163–174.
-
A set of edges in a graph is sparse if no two of these edges
belong to the same clique.
It is shown here that if a graph has girth at least 5, 6 or 8 then the
largest number of edges in a sparse set in its complement is at most
8, 7 or 6 respectively;
this result is complete and best possible.
It follows that if ε > 0 then
for sufficiently large n there exists a graph with
n vertices and chromatic number greater than
n⅓−ε,
n¼−ε or
n⅙−ε whose complement
contains no sparse set with more than 8, 7 or 6 edges respectively.
A. V. Kostochka and D. R. Woodall, Density conditions for panchromatic
colourings of hypergraphs,
Combinatorica 21 (2001), 515–541.
-
Let H = (V, E) be a hypergraph.
A panchromatic t-colouring of H is a
t-colouring of its vertices such that each edge has at least one
vertex of each colour;
and H is panchromatically t-choosable if, whenever
each vertex is given a list of t colours, the vertices can be coloured
from their lists in such a way that each edge receives at least t
different colours.
The Hall ratio of H is
-
h(H) = min
{|⋃F| / |F| :
∅ ≠ F ⊆ E}.
Among other results, it is proved here that if every edge has at least
t vertices and
-
|⋃F| ≥
(t−1)|F| − t + 3
whenever ∅ ≠ F ⊆ E,
then H is panchromatically t-choosable,
and this condition is sharp;
the minimum ct such that every t-uniform hypergraph
with h(H) > ct
is panchromatically t-choosable satisfies
-
t − 2 + 3/(t+1) ≤
ct ≤
t − 2 + 4/(t+2);
and except possibly when t = 3 or 5,
a t-uniform hypergraph is panchromatically t-colourable if
-
|⋃F| ≥
((t ² − 2t + 2)|F| +
t − 1)/t whenever
∅ ≠ F ⊆ E,
and this condition is sharp.
This last result dualizes to a sharp sufficient condition for the chromatic
index of a hypergraph to equal its maximum degree.
A. V. Kostochka and D. R. Woodall, Choosability conjectures and multicircuits,
Discrete Math. 240 (2001), 123–143.
-
This paper starts with a discussion of several old and new conjectures about
choosability in graphs.
In particular, the list-colouring conjecture, that ch' = χ'
for every multigraph, is shown to imply that if a line graph is
(a : b)-choosable,
then it is (ta : tb)-choosable for every
positive integer t.
It is proved that
ch(H²) = χ(H²)
for many "small" graphs H,
including inflations of all circuits (connected 2-regular graphs)
with length at most 11 except possibly length 9;
and that
ch"(C) = χ"(C)
(the total chromatic number)
for various multicircuits C, mainly of even order,
where a multicircuit is a multigraph whose underlying simple graph
is a circuit.
In consequence,
it is shown that if any of the corresponding graphs H²
or T(C) is
(a : b)-choosable, then it is
(ta : tb)-choosable
for every positive integer t.
D. R. Woodall, Tutte polynomial expansions for 2-separable graphs,
Discrete Math. 247 (2002), 201–213.
-
Let \Ghat be a graph obtained from a graph G with no loops
or coloops by replacing each edge e = uw of G by a
connected graph He that has only the vertices u and
w in common with the rest of \Ghat.
Two mutually dual formulas are proved for the Tutte polynomial of
\Ghat in terms of parameters of the graphs He
and (in the one case) flow polynomials of subgraphs of G or
(in the other case) tension polynomials of contractions of G.
This generalizes results of Read and Whitehead on homeomorphism classes
of graphs.
A. M. Robertshaw and D. R. Woodall, Binding number conditions for matching
extension,
Discrete Math. 248 (2002), 169–179.
-
A graph is k-extendable if it has a matching of k edges and
every such matching can be extended to a 1-factor.
We find a sharp lower bound on the binding number, in terms of n and
k,
which suffices to ensure that a graph of order n is k-extendable.
A. V. Kostochka and D. R. Woodall, Total choosability of multicircuits I,
J. Graph Theory 40 (2002), 26–43.
-
A multicircuit is a multigraph whose underlying simple graph
is a circuit (a connected 2-regular graph).
In this pair of papers, it is proved that every multicircuit C has
total choosability (that is, list total chromatic number) ch''(C)
equal to its ordinary total chromatic number χ''(C).
In the present paper, the kernel method is used to prove this
for every multicircuit that has at least two vertices with degree less than
its maximum degree Δ.
The result is also proved for every multicircuit C for which
χ''(C) ≥ Δ + 2.
A. V. Kostochka and D. R. Woodall, Total choosability of multicircuits II,
J. Graph Theory 40 (2002), 44–67.
-
A multicircuit is a multigraph whose underlying simple graph
is a circuit (a connected 2-regular graph).
In this paper, the method of Alon and Tarsi is used to prove that all
multicircuits of even order, and some regular and near-regular multicircuits
of odd order, have total choosability (that is, list total chromatic number)
equal to their ordinary total chromatic number.
This completes the proof that every multicircuit has total choosability
equal to its total chromatic number.
In the process, the total chromatic numbers of all multicircuits are
determined.
O. V. Borodin and D. R. Woodall,
Cyclic colorings of 3-polytopes with large maximum face size,
SIAM J. Discrete Math. 15 (2002), 143–154.
-
A cyclic colouring of a plane graph is a vertex colouring in which,
for each face f, all the vertices in the boundary of f
have different colours.
It is proved that if G is a 3-polytope (3-connected plane graph)
with maximum face size Δ*, then G is cyclically
(Δ* + 1)-colourable
provided that Δ* is large enough.
The figure Δ* + 1 is sharp.
D. R. Woodall,
Defective choosability results for outerplanar and related graphs,
Discrete Math. 258 (2002), 215–223.
-
It is known that if every vertex v of an outerplanar graph G
is given a list
L(v) of at least two colours, then G has an
(L,2)*-colouring;
that is, one can colour each vertex with a colour
from its own list so that no vertex has more than two neighbours
with the same colour as itself.
It is proved here that if, in addition,
|L(u) ∩ L(v)| ≤ 1
for each edge uv, or
|L(u) ∪ L(v)| ≥ 4
for each edge uv, then
G has an (L,1)*-colouring, and if
|L(u) ∪ L(v)| ≥ 5
for each edge uv then
G has an (L,0)*-colouring (a proper L-colouring).
All possible choosability results of these types for outerplanar graphs,
K2,3-minor-free graphs and
K4-minor-free graphs are also described here.
A. Prowse and D. R. Woodall,
Choosability of powers of circuits,
Graphs Combin. 19 (2003), 137–144.
-
It is proved that ch(G) = χ(G) if
G = Cn p,
the p th power of the circuit graph Cn, or if
G is a uniform inflation of such a graph.
The proof uses the method of Alon and Tarsi.
As a corollary, the (a : b)-choosability
conjectures hold for all such graphs.
D. R. Woodall,
Defective choosability of graphs with no edge-plus-independent-set minor,
J. Graph Theory 45 (2004), 51–56.
-
It is proved that, if s ≥ 2, a graph that does not have
K2 + \bar Ks = K1 + K1,s
as a minor is (s,1)*-choosable.
This completes the proof that such a graph is
(s+1−d,d)*-choosable
whenever 0 ≤ d ≤ s−1.
A. V. Kostochka and D. R. Woodall,
Irreducible hypergraphs for Hall-type conditions,
and arc-minimal digraph expanders,
European J. Combin., 26 (2005), 1119–1138.
-
Suppose that a hypergraph H = (V,E)
satisfies a Hall-type condition of the form
|⋃F| ≥ r|F| + δ
whenever ∅ ≠ F ⊆ E,
but that this condition fails if any vertex (element)
is removed from any edge (set) in E.
How large an edge can H contain?
It is proved here that there is no upper bound to the size of
an edge if r is irrational, but that if
r = p/q
as a rational in its lowest terms then H can have no edge with
more than
max{p,p+⌈δ⌉} vertices
(and if δ < 0 then H must have an edge with at most
⌈(p − 1)/q⌉ vertices).
If δ ≤ 0 then the upper bound p is sharp,
but if δ > 0 then the bound p+⌈δ⌉ can be
improved in some cases (we conjecture, in most cases).
As a generalization of this problem,
suppose that a digraph D = (V,A) satisfies an
expansion condition of the form
|N+(X) \ X| ≥
r|X| + δ
whenever ∅ ≠ X ⊆ S,
where S is a fixed subset of V, but that this condition
fails if any arc is removed from D.
It is proved that if r = p/q as a rational
in its lowest terms, then every vertex of S has outdegree at most
max{p+q, p+q+⌈δ⌉}, and at most
max{p, p+⌈δ⌉} if S is independent,
but that if r is irrational then the vertices of S can have
arbitrarily large outdegree.
D. R. Woodall,
Total 4-choosability of series-parallel graphs,
Electronic J. Combin. 13 (2006), #R97, 36pp.
-
It is proved that, if G is a K4-minor-free graph with
maximum degree 3, then G is totally 4-choosable;
that is, if every element (vertex or edge) of G is assigned a list
of 4 colours, then every element can be coloured with a colour
from its own list in such a way that every two adjacent or incident
elements are coloured with different colours.
Together with other known results, this shows that the
List-Total-Colouring Conjecture, that ch"(G) = χ"(G) for
every graph G, is true for all K4-minor-free graphs
and, therefore, for all outerplanar graphs.
T. J. Hetherington and D. R. Woodall,
Edge and total choosability of near-outerplanar graphs,
Electronic J. Combin. 13 (2006), #R98, 7pp.
-
It is proved that, if G is a K4-minor-free
graph with maximum degree Δ ≥ 4, then
G is totally (Δ+1)-choosable;
that is, if every element (vertex or edge) of G is assigned a list
of Δ+1 colours, then every element can be coloured with a
colour from its own list in such a way that every two adjacent or
incident elements are coloured with different colours.
Together with other known results, this shows that the
List-Total-Colouring Conjecture, that ch"(G) = χ"(G) for
every graph G, is true for all K4-minor-free graphs.
The List-Edge-Colouring Conjecture is also known to be true for
these graphs.
As a fairly straightforward consequence, it is proved that both
conjectures hold also for all K2,3-minor free graphs
and all (\bar K2 + (K1 ∪ K2))-minor-free
graphs.
D. R. Woodall,
Some totally 4-choosable multigraphs,
Discuss. Math. Graph Theory 27 (2007), 425–455.
-
It is proved that if G is a multigraph with maximum degree 3,
and every submultigraph of G has average degree at most 2½
and is different from one forbidden configuration
C4+ with
average degree exactly 2½, then G is totally 4-choosable;
that is, if every element (vertex or edge) of G is assigned a list
of 4 colours, then every element can be coloured with a colour
from its own list in such a way that no two adjacent or incident
elements are coloured with the same colour.
This shows that the List-Total-Colouring Conjecture, that
ch"(G) = χ"(G) for every multigraph G,
is true for all multigraphs of this type.
As a consequence, if G is a graph with maximum degree 3 and girth
at least 10 that can be embedded in the plane, projective plane,
torus or Klein bottle, then ch"(G) = χ"(G) = 4.
Some further total choosability results are discussed for planar
graphs with sufficiently large maximum degree and girth.
D. R. Woodall,
The average degree of an edge-chromatic critical graph,
Discrete Math. 308 (2008), 803–819.
-
A graph G with maximum degree Δ and edge chromatic number
χ'(G) > Δ is edge-Δ-critical if
χ'(G−e) = Δ for every edge e of G.
New lower bounds are given for the average degree of an
edge-Δ-critical graph, which improve on the
best bounds previously known for most values of Δ.
Examples of edge-Δ-critical graphs are also given.
In almost all cases,
there remains a large gap between the best lower bound known and the
smallest average degree of any known edge-Δ-critical graph.
D. R. Woodall,
The average degree of an edge-chromatic critical graph II,
J. Graph Theory 56 (2007), 194–218.
-
A graph G with maximum degree Δ and edge chromatic number
χ'(G) > Δ is edge-Δ-critical if
χ'(G−e) = Δ for every edge e of G.
It is proved that the average degree of an
edge-Δ-critical graph is
at least (2/3)(Δ+1) if Δ ≥ 2,
at least (2/3)Δ+1 if Δ ≥ 8, and
at least (2/3)(Δ+2) if Δ ≥ 15.
For large Δ, this improves on the best bound previously known,
which was roughly (1/2)(Δ + √(2Δ)).
But see the following Erratum.
D. R. Woodall,
Erratum: The average degree of an edge-chromatic critical graph II,
J. Graph Theory 92 (2019), 488–490.
-
In [D. R. Woodall, The average degree of an edge-chromatic critical graph II,
J. Graph Theory 56 (2007), 194–218] it was claimed that the
average degree of an edge-chromatic critical graph with maximum degree
Δ is
at least (2/3)(Δ+1) if Δ ≥ 2,
at least (2/3)Δ+1 if Δ ≥ 8, and
at least (2/3)(Δ+2) if Δ ≥ 15.
Unfortunately there were mistakes in the proof of the last two of these
results, which are now proved only if Δ ≥ 18 and
Δ ≥ 30 respectively.
T. J. Hetherington and D. R. Woodall,
List-colouring the square of a K4-minor-free graph,
Discrete Math. 308 (2008), 4037–4043.
-
Let G be a K4-minor-free
graph with maximum degree Δ.
It is known that if Δ ∈ {2,3} then
G² is (Δ + 2)-degenerate, so that
χ(G²) ≤ ch(G²) ≤ Δ + 3.
It is also known that if Δ ≥ 4 then
G² is
(⌊3Δ/2⌋ + 1)-degenerate and
χ(G²) ≤ ⌊3Δ/2⌋ + 1.
It is proved here that if Δ ≥ 4 then
G² is ⌈3Δ/2⌉-degenerate and
ch(G²) ≤ ⌊3Δ/2⌋ + 1.
These results are sharp.
D. R. Woodall,
An inverse binomial function and graph colourings,
Bull. Inst. Combin. Appl. 53 (2008), 73–76.
-
The expression ½(1 + √(8k+1)) occurs
in several different extremal results, especially involving graph
colourings.
These known results are briefly presented.
Z.-F. Zhang, D. R. Woodall, B. Yao, J.-W. Li, X.-E. Chen and L. Bian,
Adjacent strong edge colorings and total colorings of regular graphs,
Science in China Series A: Mathematics
52 (2009), 973–980.
-
It is conjectured that
χ'as(G) = χt(G)
for every k-regular graph G with no C5
component (k > 2).
This conjecture is shown to be true for many classes of graphs, including:
graphs of type 1; 2-regular, 3-regular and
(|V(G)|−2)-regular
graphs; bipartite graphs; balanced complete multipartite
graphs; k-cubes; and joins of two matchings or cycles.
R. G. Wood and D. R. Woodall,
Defective choosability of graphs without small minors,
Electronic J. Combin. 16 (2009), #R92, 13pp.
-
For each proper subgraph H of K5,
we determine all pairs (k,d) such that every
H-minor-free graph is
(k,d)*-choosable or
(k,d)−-choosable.
The main structural lemma is that the only 3-connected
(K5−e)-minor-free graphs are wheels,
the triangular prism, and K3,3;
this is used to prove that every
(K5−e)-minor-free graph is
4-choosable and (3,1)-choosable.
A. V. Kostochka, L. Özkahya and D. R. Woodall,
A Brooks-type bound for squares of K4-minor-free graphs,
Discrete Math. 309 (2009), 6572–6584.
-
Refining a bound by Lih, Wang and Zhu, we prove that if the square
G² of a K4-minor-free
graph G with maximum degree Δ ≥ 6
does not contain a complete subgraph on
⌊3Δ/2⌋ + 1 vertices,
then G² is ⌊3Δ/2⌋-colorable.
D. R. Woodall,
The average degree of a multigraph critical with respect to
edge or total choosability,
Discrete Math. 310 (2010), 1167–1171.
-
Let G be a multigraph with maximum degree at most
Δ ≥ 3
such that ch'(G) > Δ or
ch"(G) > Δ+1 and G is
minimal with this property.
A new proof is given for the result (which was already known, apart
from a simple calculation) that the average degree of G
is greater than √(2Δ) except possibly in the second
case when Δ = 5.
D. R. Woodall,
More elementary lower bounds on the matching number of a bipartite graph,
Bull. Inst. Combin. Appl. 58 (2010), 99–102.
-
Four lower bounds are proved for the matching number of a bipartite
graph, two of which were conjectured by Ermelinda DeLaViña's
conjecture-making program Graffiti.pc.
D. R. Woodall,
The independence number of an edge-chromatic critical graph,
J. Graph Theory 66 (2011), 98–103.
-
A graph G with maximum degree Δ and edge chromatic number
χ'(G) > Δ is edge-Δ-critical if
χ'(G−e) = Δ for every edge
e of G.
It is proved here that the vertex independence number of an
edge-Δ-critical graph of order n is less than 3n/5.
For large Δ, this improves on the best bound previously
known, which was roughly 2n/3;
the bound conjectured by Vizing, which would be best possible, is
n/2.
A. V. Kostochka, M. Stiebitz and D. R. Woodall,
Ohba's conjecture for graphs with independence number five,
Discrete Math. 311 (2011), 996–1005.
-
K. Ohba has conjectured that if G is a k-chromatic
graph with at most 2k+1 vertices, then the list chromatic
number or choosability ch(G) of G is equal to its
chromatic number χ(G), which is k.
It is known that this holds if G has independence number at
most three.
It is proved here that it holds if G has independence number at
most five.
In particular, and equivalently, it holds if G is a complete
k-partite graph and each part has at most five vertices.
D. R. Woodall,
Defective choosability of graphs in surfaces,
Discuss. Math. Graph Theory 31 (2011), 441–459.
-
It is known that if G is a graph that can be drawn
without edges crossing in a surface with Euler characteristic
ε, and k and d are positive integers
such that k ≥ 3 and d is
sufficiently large in terms of k and ε, then
G is (k,d)*-colorable;
that is, the vertices of G can be colored with k
colors so that each vertex has at most d neighbors with the
same color as itself.
In this paper, the known lower bound on d that suffices for
this is reduced, and an analogous result is proved for list colorings
(choosability).
Also, the recent result of Cushing and Kierstead, that every planar
graph is (4,1)*-choosable, is extended to
K3,3-minor-free and
K5-minor-free graphs.
T. J. Hetherington and D. R. Woodall,
List-colouring the square of an outerplanar graph,
Ars Combin. 101 (2011), 333–342.
-
It is proved that if G is a K2,3-minor-free
graph with maximum degree Δ, then
Δ + 1 ≤ χ(G²) ≤ ch(G²) ≤ Δ + 2
if Δ ≥ 3, and
ch(G²) = χ(G²) = Δ + 1 if
Δ ≥ 6.
All inequalities here are sharp, even for outerplanar graphs.
D. R. Woodall,
Colourfully panconnected subgraphs II,
Ars Combin. 106 (2012), 367–380.
-
Let G be a connected k-colourable graph of order
n ≥ k.
A subgraph H of G is k-colourfully panconnected in G
if there is a k-colouring of G such that the colours are
close together in H, in two different senses (called
variegated and panconnected) to be made precise.
Let sk(G)
denote the smallest number of edges in a spanning
k-colourfully panconnected subgraph H of G.
It is conjectured that
sk(G) = n−1 if
k ≥ 4 and G is not a circuit (a connected
2-regular graph) with length ≡ 1 (mod k).
It is proved that
sk(G) = n−1 if
G contains no circuit with length ≡ 1
(mod k), and
sk(G) ≤ 2n−k−1
whenever k ≥ 4.
D. Bauer, N. Kahl, E. Schmeichel, D. R. Woodall and M. Yatauro,
Improving theorems in a best monotone sense,
Congressus Numerantium 216 (2013), 87–95.
-
We demonstrate how certain theorems can be improved when we know
the degree sequence of a graph. In particular,
let τ(G) and bind(G) be the toughness and the
binding number, respectively, of a graph G.
We show how a recent best possible lower bound on τ(G)
in terms of bind(G), when bind(G) ≥ 2,
can be improved when combined with a knowledge of the degree sequence of
G.
D. Bauer, N. Kahl, E. Schmeichel, D. R. Woodall and M. Yatauro,
Toughness and binding number,
Discrete Applied Math. 165 (2014), 60–68.
-
Let τ(G) and bind(G) be the toughness and the
binding number, respectively, of a graph G.
Woodall observed in 1973 that
τ(G) ≥ bind(G)−1.
In this paper, we obtain best possible improvements of Woodall's
inequality except when
(1+√5)/2 < bind(G) < 2
and bind(G) has an even denominator when expressed in lowest terms.
O. V. Borodin, A. O. Ivanova and D. R. Woodall,
Light C4 and C5 in 3-polytopes
with minimum degree 5,
Discrete Math. 334 (2014), 63–69.
-
Let wP(Cl)
(wT(Cl))
be the minimum integer k with the property that every 3-polytope
(respectively, every plane triangulation) with minimum
degree 5 has an l-cycle with weight, defined as the degree-sum
of all vertices, at most k.
In 1998, O. V. Borodin and D. R. Woodall proved
wT(C4) = 25 and
wT(C5) = 30.
We prove that
wP(C4) = 26 and
wP(C5) = 30.
D. Bauer, H. J. Broersma, J. van den Heuvel, N. Kahl,
A. Nevo, E. Schmeichel, D. R. Woodall and M. Yatauro,
Best monotone degree conditions for graph properties: a survey,
Graphs Combin. 31 (2015), 1–22.
-
We survey sufficient degree conditions, for a variety of graph properties,
that are best possible in the same sense that Chvátal's well-known
degree condition for hamiltonicity is best possible.
D. Bauer, A. Nevo, E. Schmeichel, D. R. Woodall and M. Yatauro,
Best monotone degree conditions for binding number and cycle structure,
Discrete Applied Math. 195 (2015), 8–17.
-
Woodall has shown that every 3/2-binding graph is hamiltonian.
In this paper, we consider best monotone degree conditions for a
b-binding graph to be hamiltonian, for
1 ≤ b < 3/2.
We first establish such a condition for b = 1.
We then give a best monotone degree condition for a b-binding graph
to be 1-tough, for 1 < b < 3/2,
and note it is possible that this condition is also the
best monotone degree condition for a b-binding graph to be
hamiltonian, for 1 < b < 3/2.
D. R. Woodall,
Towards size reconstruction from fewer cards,
Discrete Math. 338 (2015), 2514–2522.
-
It is proved that if two graphs of order n have n−p
cards (vertex-deleted subgraphs) in common, where p ≥ 3,
and n is large enough compared with p, then the numbers
of edges in the two graphs differ by at most p−2.
This is a modest but nontrivial improvement of the easy result
that these numbers differ by at most p.
D. R. Woodall,
The average degree of a subcubic edge-chromatic critical graph,
J. Graph Theory 91 (2019), 103–121.
-
A graph G is 3-critical if Δ(G) = 3,
χ′(G) = 4, and
χ′(G−e) = 3
for every edge e of G.
The 3-critical graphs include P* (the Petersen graph
with a vertex deleted), and subcubic graphs that are
Hajós joins of copies of P*.
Building on a recent paper of Cranston and Rabern,
it is proved here that if G is 3-critical and not P* nor
a Hajós join of two copies of P*,
then G has average degree at least 68/25 = 2.72;
this bound is sharp, as it is the average degree of
a Hajós join of three copies of P*.
D. R. Woodall's legacy university home page
start of current page