The performance of a D-Wave Vesuvius quantum annealer was recently compared to a suite of classical algorithms on a class of constraint satisfaction instances based on frustrated loops. However, the construction of these instances leads the maximum coupling strength to increase with problem size. As a result, larger instances are subject to amplified analog control error, and are effectively annealed at higher temperatures in both hardware and software. We generate similar constraint satisfaction instances with limited range of coupling strength and perform a similar comparison to classical algorithms. On these instances the D-Wave Vesuvius processor, run with a fixed 20μs anneal time, shows a scaling advantage over the software solvers for the hardest regime studied. This scaling advantage opens the possibility of quantum speedup on these problems. Our results support the hypothesis that performance of D-Wave Vesuvius processors is heavily influenced by analog control error, which can be reduced and mitigated as the technology matures.

Recent advances bring within reach the viability of solving combinatorial problems using a quantum annealing algorithm implemented on a purpose-built platform that exploits quantum properties. However, the question of how to tune the algorithm for most effective use in this framework is not well understood. In this paper we describe some operational parameters that drive performance, discuss approaches for mitigating sources of error, and present experimental results from a D-Wave Two quantum annealing processor.

In 1998 the second author proved that there is an $ε>0$ such that every graph satisfies $χ ≤ ⌈ (1-ε)(Δ+1)+εω⌉$. The first author recently proved that any graph satisfying $ω > (2/3)(Δ+1)$ contains a stable set intersecting every maximum clique. In this note we exploit the latter result to give a much shorter, simpler proof of the former. We include, as a certificate of simplicity, an appendix that proves all intermediate results with the exception of Hall's Theorem, Brooks' Theorem, the Lov\'asz Local Lemma, and Talagrand's Inequality.

A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the $q$-backbone colouring problem, these minimum distances are either $q$ or $1$, depending on whether or not the edge is in the backbone. In this paper we consider the list version of this problem, with particular focus on colours in $\Z_p$ -- this problem is closely related to the problem of circular choosability. We first prove that the list circular $q$-backbone chromatic number of a graph is bounded by a function of the list chromatic number. We then consider the more general problem in which each edge is assigned an individual distance between its endpoints, and provide bounds using the Combinatorial Nullstellensatz. Through this result and through structural approaches, we achieve good bounds when both the graph and the backbone belong to restricted families of graphs.

We introduce the notion of an Eulerian graph being strongly even cycle decomposable, and note that a few basic classes have this property. We then prove that several fundamental composition operations that preserve the property of being Eulerian also preserve the property of being strongly even cycle decomposable. Our composition operations imply that all simple Eulerian k-partite graphs are strongly even cycle decomposable, with the exception of K_5.

Chudnovsky and Seymour's structure theorem for claw-free graphs has led to a multitude of recent results that exploit two structural operations: compositions of strips and thickenings In this paper we consider the latter, proving that every claw-free graph has a unique optimal antithickening, where our definition of optimal is chosen carefully to respect the structural foundation of the graph. Furthermore, we give an algorithm to find the optimal antithickening in $O(m^2)$ time. For the sake of both completeness and ease of proof, we prove stronger results in the more general setting of trigraphs.

Reed's well-known ω, Δ, χ conjecture proposes that every graph satisfies $χ ≤ ⌈ (1/2)(Δ+1+ω)⌉$. The second author formulated a local strengthening of this conjecture that considers a bound supplied by the neighbourhood of a single vertex. Following the idea that the chromatic number cannot be greatly affected by any particular stable set of vertices, we propose a further strengthening that considers a bound supplied by the neighbourhoods of two adjacent vertices. We provide some fundamental evidence in support, namely that the stronger bound holds in the fractional relaxation and holds for both quasi-line graphs and graphs with stability number two. We also conjecture that in the fractional version, we can push the locality even further.

The second author's ω, Δ, χ conjecture proposes that every graph satisties χ ≤ ⌈(1/2)(Δ+1+ω)⌉. In this paper we prove that the conjecture holds for all claw-free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way we discuss a stronger local conjecture, and prove that it holds for claw-free graphs with a three-colourable complement. To prove our results we introduce a very useful χ-preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so-called skeletal graphs.

Consider an undirected graph G and a subgraph H of G, on the same vertex set. The q-backbone chromatic number BBCq(G,H) is the minimum k such that G can be properly coloured with colours from {1, ..., k}, and moreover for each edge of H, the colours of its ends differ by at least q. In this paper we focus on the case when G is planar and H is a forest. We give a series of NP-hardness results as well as upper bounds for BBCq(G,H), depending on the type of the forest (matching, galaxy, spanning tree). Eventually, we discuss a circular version of the problem.

A lemma of Fouquet implies that a claw-free graph contains an induced $C_5$, contains no odd hole, or is quasi-line. In this paper we use this result to give an improved shortest-odd-hole algorithm for claw-free graphs by exploiting the structural relationship between line graphs and quasi-line graphs suggested by Chudnovsky and Seymour's structure theorem for quasi-line graphs. Our approach involves reducing the problem to that of finding a shortest odd cycle of length $≥ 5$ in a graph. Our algorithm runs in $O(m^2+n^2\log n)$ time, improving upon Shrem, Stern, and Golumbic's recent $O(nm^2)$ algorithm, which uses a local approach. The best known recognition algorithms for claw-free graphs run in $O(m^{1.69}) ∩ O(n^{3.5})$ time, or $O(m^2) ∩ O(n^{3.5})$ without fast matrix multiplication.

King, Lu, and Peng recently proved that for $Δ≥ 4$, any $K_Δ$-free graph with maximum degree Δ has fractional chromatic number at most $Δ-(2/67)$ unless it is isomorphic to $C_5\boxtimes K_2$ or $C_8^2$. Using a different approach we give improved bounds for $Δ≥ 6$ and pose several related conjectures. Our proof relies on a weighted local generalization of the fractional relaxation of Reed's ω, Δ, χ conjecture.

Reed's ω, Δ, χ conjecture proposes that every graph satisfies $χ≤ ⌈(1/2)(Δ+1+ω)⌉$; it is known to hold for all claw-free graphs. In this paper we consider a local strengthening of this conjecture. We prove the local strengthening for line graphs, then note that previous results immediately tell us that the local strengthening holds for all quasi-line graphs. Our proofs lead to polytime algorithms for constructing colourings that achieve our bounds: $O(n^2)$ for line graphs and $O(n^3m^2)$ for quasi-line graphs. For line graphs, this is faster than the best known algorithm for constructing a colouring that achieves the bound of Reed's original conjecture.

It was recently proved that any graph satisfying $ω > (2/3)(Δ+1)$ contains a stable set hitting every maximum clique. In this note we prove that the same is true for graphs satisfying $ω ≥ (2/3)(Δ+1)$ unless the graph is the strong product of $K_{ω/2}$ and an odd hole. We also provide a counterexample to a recent conjecture on the existence of a stable set hitting every sufficiently large maximal clique.

As proved by Kahn, the chromatic number and fractional chromatic number of a line graph agree asymptotically. That is, for any line graph $G$ we have $χ(G) ≤ (1+o(1))χ_f(G)$. We extend this result to quasi-line graphs, an important subclass of claw-free graphs. Furthermore we prove that we can construct a colouring that achieves this bound in polynomial time, giving us an asymptotic approximation algorithm for the chromatic number of quasi-line graphs.

Let $Δ(G)$ be the maximum degree of a graph $G$. Brooks' theorem states that the only connected graphs with chromatic number $χ(G)=Δ(G)+1$ are complete graphs and odd cycles. We prove a fractional analogue of Brooks' theorem in this paper. Namely, we classify all connected graphs $G$ such that the fractional chromatic number $χ_f(G)$ is at least $Δ(G)$. These graphs are complete graphs, odd cycles, $C^2_8$, $C_5\boxtimes K_2$, and graphs whose clique number $ω(G)$ equals the maximum degree $Δ(G)$. Among the two sporadic graphs, the graph $C^2_8$ is the square graph of cycle $C_8$ while the other graph $C_5\boxtimes K_2$ is the strong product of $C_5$ and $K_2$. In fact, we prove a stronger result; if a connected graph $G$ with $Δ(G)≥ 4$ is not one of the graphs listed above, then we have $χ_f(G)≤ Δ(G)- 2/67$.

We show that every cubic bridgeless graph G has at least 2^(|V(G)|/3656) perfect matchings. This confirms an old conjecture of Lovasz and Plummer. The arXiv version of the paper uses a different definition of a burl from the journal version of the paper and a different proof of Lemma 18 is given. This simplifies the exposition of our arguments throughout the whole paper.

Rabern recently proved that any graph with ω ≥ (3/4)(Δ+1) contains a stable set meeting all maximum cliques. We strengthen this result, proving that such a stable set exists for any graph with omega > (2/3)(Δ+1). This is tight, i.e. the inequality in the statement must be strict. The proof relies on finding an independent transversal in a graph partitioned into vertex sets of unequal size.

Reed conjectured that for every ε>0 and Δ there exists g such that the fractional total chromatic number of a graph with maximum degree Δ and girth at least g is at most Δ+1+ε. We prove the conjecture for Δ=3 and for even Δ≥4 in the following stronger form: For each of these values of Δ, there exists g such that the fractional total chromatic number of any graph with maximum degree Δ and girth at least g is equal to Δ+1.

An equivalence graph is a disjoint union of cliques, and the equivalence number $eq(G)$ of a graph $G$ is the minimum number of equivalence subgraphs needed to cover the edges of $G$. We consider the case in which $G$ is a line graph, giving improved upper and lower bounds: $(1/3) \log_2\log_2 χ(G) ≤ eq(L(G)) ≤ 2\log_2\log_2 χ(G) + 2$. This disproves a recent conjecture that $eq(L(G))$ is at most three for triangle-free $G$; indeed it can be arbitrarily large. To bound $eq(L(G))$ we bound the closely-related invariant $σ(G)$, which is the minimum number of orientations of $G$ such that for two incident edges $e,f$ incident to $v$, both $e$ and $f$ are oriented out of $v$ in some orientation. When $G$ is triangle-free, $σ(G)=eq(L(G))$, and we prove that even in this case it is NP-hard to decide whether or not $σ(G)≤ 3$.

An i-triangulated graph is a graph in which every odd cycle has two non-crossing chords; i-triangulated graphs form a subfamily of perfect graphs. A slightly more general family of perfect graphs are clique-separable graphs. A graph is clique-separable precisely if every induced subgraph either has a clique cutset, or is a complete multipartite graph or a clique joined to an arbitrary bipartite graph. We exhibit a polynomial time algorithm for finding a maximum-weight induced k-partite subgraph of an i-triangulated graph, and show that the problem of finding a maximum-size bipartite induced subgraph in a clique-separable graph is NP-complete.

We show that the firefighter problem is NP-complete for cubic graphs. We also show that given a rooted tree of maximum degree three in which every leaf is at the same distance from the root, it is NP-complete to decide whether or not there is a strategy that protects every leaf from the fire, which starts at the root. By contrast, we describe a polynomial time algorithm to decide if it is possible to save a given subset of the vertices of a graph with maximum degree three, provided the fire breaks out at a vertex of degree at most two.

A quasi-line graph is a graph in which the neighbourhood of any vertex can be covered by two cliques; every line graph is a quasi-line graph. Reed conjectured that for any graph $G$, $χ(G) ≤ ⌈ (1/2)(Δ(G)+1+ω(G))⌉$. We prove that the conjecture holds if $G$ is a quasi-line graph, extending a result of King, Reed and Vetta, who proved the conjecture for line graphs, and improving the bound of $χ(G) ≤ (3/2)ω(G)$ given by Chudnovsky and Ovetsky.

It was conjectured by Reed that for any graph $G$, the graph's chromatic number $χ(G)$ is bounded above by $⌈(1/2)(Δ(G) +1 + ω(G))⌉$, where $Δ(G)$ and $ω(G)$ are the maximum degree and clique number of $G$, respectively. In this paper we prove that this bound holds if $G$ is the line graph of a multigraph. The proof yields a polynomial time algorithm that takes a line graph $G$ and produces a colouring that achieves our bound.

We show that the firefighter problem is NP-complete for trees of maximum degree three, but in P for graphs of maximum degree three if the fire breaks out at a vertex of degree at most two.

An indecomposable permutation π on [n] is one such that π([m])=[m] for no m<n. We consider indecomposable permutations and give a new, inclusive enumerative recurrence for them. This recurrence allows us to generate all indecomposable permutations of length n in transposition Gray code order, in constant amortized time (CAT). We also present a CAT generation algorithm for indecomposable permutations which is based on the Johnson–Trotter algorithm for generating all permutations of length n. The question of whether or not there exists an adjacent transposition Gray code for indecomposable permutations remains open.

Motivation: Understanding principles of cellular organization and function can be enhanced if we detect known and predict still undiscovered protein complexes within the cell's protein–protein interaction (PPI) network. Such predictions may be used as an inexpensive tool to direct biological experiments. The increasing amount of available PPI data necessitates an accurate and scalable approach to protein complex identification.
Results: We have developed the Restricted Neighborhood Search Clustering Algorithm (RNSC) to efficiently partition networks into clusters using a cost function. We applied this cost-based clustering algorithm to PPI networks of Saccharomyces cerevisiae, Drosophila melanogaster and Caenorhabditis elegans to identify and predict protein complexes. We have determined functional and graph-theoretic properties of true protein complexes from the MIPS database. Based on these properties, we defined filters to distinguish between identified network clusters and true protein complexes.
Conclusions: Our application of the cost-based clustering algorithm provides an accurate and scalable method of detecting and predicting protein complexes within a PPI network.
Availability: The RNSC algorithm and data processing code are available upon request from the authors.