KPPY 96

The problem of maximising the number of cliques among n-vertex graphs from various graph classes has received considerable attention. We investigate this problem for the class of $1$-planar graphs, i.e. graphs that can be drawn in the plane in such a way that each edge crosses at most 1 other edge, where we determine precisely the maximum total number of cliques as well as the maximum number of cliques of any fixed size. We also precisely characterise the extremal graphs for these problems.

This is joint work with Kevin Hendrey, Abhishek Methuku, Casey Tompkins and Xin Zhang.

The switch homomorphism problem Switch(H) for a signed graph H is known to be polynomial time solvable if H has a switch-core with at most two edges and is otherwise NP-complete. We present results towards a similar dichotomy classification for the list version of the problem.

Thomassen proved that all girth $5$ graphs embeddable in the torus or projective plane are $3$-colourable. Thomas and Walls showed that all girth $5$ graphs embeddable in the Klein Bottle are $3$-colourable. I'll show a generalization of both of these results: Every $4$-critical triangle free graph satisfies \(e(G) \geq (5v(G)+2)/3\).

This is joint work with Evelyne Smith Roberge.

The WL dimension $\mathsf{dim}_{WL}$ of a graph $G$ introduced by Grohe is the least $d$ such that the $d$-dimensional Weisfeiler-Leman (WL) algorithm distinguishes $G$ from every graph not isomorphic to $G$. The WL dimension of a class $\mathcal{G}$ of graphs is defined to be $\mathsf{max}\{\mathsf{dim}_{WL}(G)\mid G\in \mathcal{G}\}$ if this maximum exists and $\infty$ otherwise.

The upper bounds on the WL dimension have been shown for many natural graph classes, including planar graphs, trees, graphs of bounded tree width, graphs of bounded genus, all graph classes with excluded minors, interval graphs, and graphs of bounded rank width.

It was shown by Grohe and Neuen (2019) that the class of graphs of rank width $r$ has WL dimension at most $3r+4$. However, for particular subclasses of graphs of bounded rank width, this bound does not seem to be tight.

A distance-hereditary graph $G$ is a graph such that the distances in any connected induced subgraph of $G$ are the same as they are in $G$. The distance-hereditary graphs have rank width at most 1; therefore, their WL dimension is at most 7 by the above mentioned result.

In this work, we prove that the WL dimension of distance-hereditary graphs is precisely $2$. This is joint work with Ilia Ponomarenko and Roman Nedela.