BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Richard C. Brewster

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.CODiscrete MathematicsComputational Complexity

Catalog footprint

Research overview

4works
3topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

4 publications

preprint2022arXiv

Characterizing Circular Colouring Mixing for pq<4\frac{p}{q}<4

Given a graph GG, the kk-mixing problem asks: Can one obtain all kk-colourings of GG, starting from one kk-colouring ff, by changing the colour of only one vertex at a time, while at each step maintaining a kk-colouring? More generally, for a graph HH, the HH-mixing problem asks: Can one obtain all homomorphisms G→HG \to H, starting from one homomorphism ff, by changing the image of only one vertex at a time, while at each step maintaining a homomorphism G→HG \to H? This paper focuses on a generalization of kk-colourings, namely (p,q)(p,q)-circular colourings. We show that when 2<pq<42 < \frac{p}{q} < 4, a graph GG is (p,q)(p,q)-mixing if and only if for any (p,q)(p,q)-colouring ff of GG, and any cycle CC of GG, the wind of the cycle under the colouring equals a particular value (which intuitively corresponds to having no wind). As a consequence we show that (p,q)(p,q)-mixing is closed under a restricted homomorphism called a fold. Using this, we deduce that (2k+1,k)(2k+1,k)-mixing is co-NP-complete for all k∈Nk \in \mathbb{N}, and by similar ideas we show that if the circular chromatic number of a connected graph GG is 2k+1k\frac{2k+1}{k}, then GG folds to C2k+1C_{2k+1}. We use the characterization to settle a conjecture of Brewster and Noel, specifically that the circular mixing number of bipartite graphs is 22. Lastly, we give a polynomial time algorithm for (p,q)(p,q)-mixing in planar graphs when 3≤pq<43 \leq \frac{p}{q} <4.

Open access
preprint2016arXiv

A Dichotomy Theorem for Circular Colouring Reconfiguration

The "reconfiguration problem" for circular colourings asks, given two (p,q)(p,q)-colourings ff and gg of a graph GG, is it possible to transform ff into gg by changing the colour of one vertex at a time such that every intermediate mapping is a (p,q)(p,q)-colouring? We show that this problem can be solved in polynomial time for 2≤p/q<42\leq p/q <4 and is PSPACE-complete for p/q≥4p/q\geq 4. This generalizes a known dichotomy theorem for reconfiguring classical graph colourings.

Open access
preprint2016arXiv

The complexity of signed graph and edge-coloured graph homomorphisms

We study homomorphism problems of signed graphs from a computational point of view. A signed graph (G,Σ)(G,Σ) is a graph GG where each edge is given a sign, positive or negative; Σ⊆E(G)Σ\subseteq E(G) denotes the set of negative edges. Thus, (G,Σ)(G, Σ) is a 22-edge-coloured graph with the property that the edge-colours, {+,−}\{+, -\}, form a group under multiplication. Central to the study of signed graphs is the operation of switching at a vertex, that results in changing the sign of each incident edge. We study two types of homomorphisms of a signed graph (G,Σ)(G,Σ) to a signed graph (H,Π)(H,Π): ec-homomorphisms and s-homomorphisms. Each is a standard graph homomorphism of GG to HH with some additional constraint. In the former, edge-signs are preserved. In the latter, edge-signs are preserved after the switching operation has been applied to a subset of vertices of GG. We prove a dichotomy theorem for s-homomorphism problems for a large class of (fixed) target signed graphs (H,Π)(H,Π). Specifically, as long as (H,Π)(H,Π) does not contain a negative (respectively a positive) loop, the problem is polynomial-time solvable if the core of (H,Π)(H,Π) has at most two edges, and is NP-complete otherwise. (Note that this covers all simple signed graphs.) The same dichotomy holds if (H,Π)(H,Π) has no negative digons, and we conjecture that it holds always. In our proofs, we reduce s-homomorphism problems to certain ec-homomorphism problems, for which we are able to show a dichotomy. In contrast, we prove that a dichotomy theorem for ec-homomorphism problems (even when restricted to bipartite target signed graphs) would settle the dichotomy conjecture of Feder and Vardi.

Open access
preprint2014arXiv

Mixing Homomorphisms, Recolourings, and Extending Circular Precolourings

This work brings together ideas of mixing graph colourings, discrete homotopy, and precolouring extension. A particular focus is circular colourings. We prove that all the (k,q)(k,q)-colourings of a graph GG can be obtained by successively recolouring a single vertex provided k/q≥2col(G)k/q\geq 2col(G) along the lines of Cereceda, van den Heuvel and Johnson's result for kk-colourings. We give various bounds for such mixing results and discuss their sharpness, including cases where the bounds for circular and classical colourings coincide. As a corollary, we obtain an Albertson-type extension theorem for (k,q)(k,q)-precolourings of circular cliques. Such a result was first conjectured by Albertson and West. General results on homomorphism mixing are presented, including a characterization of graphs GG for which the endomorphism monoid can be generated through the mixing process. As in similar work of Brightwell and Winkler, the concept of dismantlability plays a key role.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.