Zhouningxin Wang: Mapping signed sparse graphs to (K_2k, M)

Datum objave: 27. 2. 2021
Seminar za diskretno matematiko
Na daljavo
ID: 919 4722 1263 – Geslo: 107221

A signed graph $(G, \sigma)$ is a graph $G$ (loops and multi-edges allowed) together with an assignment $\sigma: E(G) \to {+, -}$. A homomorphism of a signed graph $(G, \sigma)$ to $(H, \pi)$ is a mapping of vertices and edges of $G$ respectively to the vertices and edges of $H$ such that the adjacencies, the incidences, and the signs of closed walks are preserved. Motivated by reformulations of the $k$-coloring problem in this language, and especially in connection with results on $3$-coloring of planar graphs, such as Gr\"{o}tzsch's theorem, we consider bounds on the maximum average degree which are sufficient for mapping signed graphs to the signed graph $(K_{2k}, M)$ ($k\geq 3$) where the negative edges form a perfect matching. In this talk, we show that for $k=3$ the maximum average degree strictly less than $\frac{14}{5}$ is sufficient and for values of $k\geq 4$, we find the best maximum average degree bound to be $3$. Moreover, we discuss the applications of our work to signed planar graphs and propose questions similar to Steinberg's conjecture for the class of signed bipartite planar graphs.