Chetwynd and Hilton made the following \({edge-colouring \; conjecture}\): if a simple graph \(G\) satisfies \(\Delta(G) > \frac{1}{3}|V(G)|\), then \(G\) is Class \(2\) if and only if it contains an overfull subgraph \(H\) with \(\Delta(H) = \Delta(G)\). They also made the following \({total-colouring \; conjecture}\): if a simple graph \(G\) satisfies \(\Delta(G) \geq \frac{1}{2}(|V(G)|+ 1)\), then \(G\) is Type \(2\) if and only if \(G\) contains a non-conformable subgraph \(H\) with \(\Delta(H) = \Delta(G)\). Here we show that if the edge-colouring conjecture is true for graphs of even order satisfying \(\Delta(G) > \frac{1}{2}|V(G)|\), then the total-colouring conjecture is true for graphs of odd order satisfying \(\delta(G) \geq \frac{3}{4}{|V(G)|} – \frac{1}{4}\) and \(\text{def}(G) \geq 2(\Delta(G) – \delta(G) + 1)\).

We correct an omission by Mathon in his classification of symmetric \((31, 10, 3)\)-designs with a non-trivial automorphism group and find that there are a further six such designs, all with an automorphism group of order \(3\).

A \({dominating \; function}\) is a feasible solution to the LP relaxation of the minimum dominating set \(0-1\) integer program. A minimal dominating function (MDF) g is called universal if every convex combination of g and any other MDF is also a MDF. The problem of finding a universal MDF in a tree \({T}\) can also be described by a linear program. This paper describes a linear time algorithm that finds a universal MDF in \({T}\), if one exists.

Let \(H\) be a digraph whose vertices are called colours. Informally, an \(H\)-colouring of a digraph \(G\) is an assignment of these colours to the vertices of \(G\) so that adjacent vertices receive adjacent colours. In this paper we continue the study of the \(H\)-colouring problem, that is, the decision problem “Does there exist an \(H\)-colouring of a given digraph \(G\)?”. In particular, we prove that the \(H\)-colouring problem is NP-complete if the digraph \(H\) consists of a directed cycle with two chords, or two directed cycles joined by an oriented path, or is obtained from a directed cycle by replacing some arcs by directed two-cycles, so long as \(H\) does not retract to a directed cycle. We also describe a new reduction which yields infinitely many new infinite families of NP-complete \(H\)-colouring problems.

Bondy conjectures that if \(G\) is a \(2\)-edge-connected simple graph with \(n\) vertices, then at most \((2n-1)/{3}\) cycles in \(G\) will cover \(G\). In this note, we show that if \(G\) is a plane triangulation with \(n \geq 6\) vertices, then at most \((2n-3)/{3}\) cycles in \(G\) will cover \(G\).