A k-colouring of a graph is an assignment of one of k colours to each vertex so that the ends of each edge get different colours.

The reconfiguration graph of the k-colourings of graph G, denoted Rk(G), is the graph whose vertices are the k-colourings of G, and two colourings are adjacent in Rk(G) if they differ in colour on exactly one vertex. We are interested in whether the reconfiguration graph is connected, and if so, its diameter. Being connected means we can obtain any k-colouring from any other by changing the colour of one vertex at a time, while always having a k-colouring.

We call a graph recolourable if Rk(G) is connected for every k bigger than the chromatic number of G. We have characterized the graphs H such that all graphs G which don’t have H as an induced subgraph are recolourable. We have done the same for other hereditary graph classes including when two 4-vertex graphs are excluded as induced subgraphs.

We also explore graph decompositions applied to recolouring.

This is joint work with Manoj Belavadi, Owen Merkel and Ni Luh Dewi Sintiari.

Strong cocomparability graphs are the reflexive graphs whose adjacency matrix can be rearranged by a simultaneous row and column permutation to avoid the submatrix with rows $01, 10$. Strong cocomparability graphs form a subclass of cocomparability graphs (i.e., the complements of comparability graphs) and can be recognized in polynomial time. In his seminal paper, Gallai characterized cocomparability graphs in terms of a forbidden structure called asteroids. Gallai proved that cocomparability graphs are precisely those reflexive graphs which do not contain asteroids.

In this talk, I will present a characterization of strong cocomparability graphs which is analogous to Gallai's characterization for cocomparability graphs. More precisely, I will show that strong cocomparability graphs are precisely those reflexive graphs which do not contain weak edge-asteroids (a weaker version of asteroids). The characterization also leads to a polynomial time recognition algorithm for strong cocomparability graphs.

I will give a review of the state of the art on mixed cages since we introduced them in a joint work with C. Hernández, and J.J. Montellano-Ballesteros, in 2019 (see [1]). A mixed regular graph is graph G = (V ; E U A) where V (G) is the set of vertices, E(G) is the set of edges, and A(G) is the set of arcs where each vertex has z in and out arcs, and r edges. A mixed cycle is a cycle with edges and arcs, and all the arcs are traversed in the same direction, then the girth in a mixed graph is the length of the minimal mixed cycle. A [z,r;g]-a mixed graph of girth g is a mixed regular graph of girth g. Moreover, a [z, r; g]-mixed cage of girth g is a [z, r; g]-mixed graph or mini- mum order. In [1] we give simple results about this and a nice lower bound, denoted by n[1, r; g], for [1, r; g]-graphs attained for r = 2 and any girth $g \geq 3$. Recently, in 2023, Exoo in [4] proved that this bound, called now as the AHM-Bound, is attained also for r = 3 and g = 6 finding a [1, 3, 6]-cage with 30 vertices. I will show the graphs attained from Exoo in [4] using searching computational techniques, and mixed graphs of girth 5, obtained by G. Araujo, C. De la Cruz, and D. González-Moreno ([2]), using finite geometries. Moreover, in that paper, we give results on the structure of mixed cages related to connectivity and monotonicity. Also, I will talk about a recent work with L. Mendoza (see [3]), on mixed cages of girth 6 and new lower bounds for any three values $z \geq 1, r \geq 2$ and $g \geq 3$. In this work, we describe the [1,3,6]-cage given by Exoo in [4] as a subgraph with some ”added arcs” of a (4, 6)-cage or the incidence graph of a projective plane of order 3. Finally, I will give other results given by Jacay and Jacayovna in two recent conferences related to [z, r, g]-mixed graphs with few vertices using the CD(n, q)-graphs introduced by Lazebnik, Ustimenko, and Woldar in [5].

[1] Graphs and Combinatorics, 35 (5):989–999, (2019).
[2] Discrete Mathematics, 345 (5):112792, (2022).
[3] (submitted).
[4] Discrete Mathematics and Theoretical Computer Science, vol. 25:2, (2023).
[5] J. Comb. Theory, Ser. B 61 (1) 111–117 (1994).

We investigate the computational complexity of list homomorphism problems for signed graphs. The CSP dichotomy conjecture has been recently established, but several other dichotomy questions remain open, including the dichotomy classification of list homomorphism problems for signed graphs. Compared to the classical homomorphism problems, we additionally get lists of admissible targets for each vertex of the input graph in the list version.

Usually, a dichotomy classification is easier to obtain for list homomorphisms than for homomorphisms. However, this is not the case for signed graphs. The complexity classification of the list homomorphism problem proves to be challenging, and as of now, no structural classification conjecture has been proposed. I will show a structural classification in the special case of weakly balanced irreflexive and reflexive signed graphs, a conjecture previously made by Kim and Siggers. This builds up on our previous results for signed trees and separable signed graphs, which I will briefly outline as well. The proof for the irreflexive case relies on establishing an extension theorem for min orderings of (unsigned) bipartite graphs, which is interesting on its own.