KPPY 96

Pascal Gollin, Hyobin Kim, Ben Moore, Alexander Gavrilyuk.

KPPY 96

Sept 24, 2021.  4pm - 6pm.  Online

Schedule
4:00 - 4:25 Pascal Gollin
IBS Discrete Math Group at KAIST
Counting cliques in 1-planar graphs
4:30 - 4:55 Hyobin Kim
KNU
Towards a dichotomy for List Switch homomorphism for signed graphs
5:00 - 5:25 Ben Moore
Charles University
A density bound for triangle free 4-critical graphs
5:30 - 5:55 Alexander Gavrilyuk
Shimane University
The Weisfeiler-Leman dimension of distance-hereditary graphs

Abstracts





Pascal Gollin
Counting cliques in 1-planar graphs
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.




Hyobin Kim
Towards a dichotomy for List Switch homomorphism for signed graphs
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.




Ben Moore
A density bound for triangle free 4-critical graphs
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.




Alexander Gavrilyuk
The Weisfeiler-Leman dimension of distance-hereditary graphs
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.