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 nr. (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 FF 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 = X1Y1, there is a partition B2 = X2Y2 such that X1Y2 and X2Y1 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(√kpk), 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 abc 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 = (VE) 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 (K5e)-minor-free graphs are wheels, the triangular prism, and K3,3; this is used to prove that every (K5e)-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 χ'(Ge) = Δ 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) ≤ 2nk−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 np 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 χ′(Ge) = 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