2024 CMS Winter Meeting

Vancouver/Richmond, Nov 29 - Dec 2, 2024

Submission Form Plenary, Prize and Public Lectures By session By speaker Posters

Graph Coloring, Minors, and Hypergraphs (previously Graph Theory)
Org: Alexander Clow, Bojan Mohar and Ladislav Stacho (Simon Fraser University)
[PDF]

ALEXANDER CLOW, Simon Fraser University A Map Colour Theorem for Oriented Colouring [PDF]

A classical problem in graph colouring theory, dating back to Heawood, is to study the number of colours required to colour graphs embeddable on a surface of bounded Euler genus. In this talk we will present a nearly tight bound on the oriented chromatic number in terms of the Euler genus of the graph being coloured. In particular, we will show that there exists oriented graphs with Euler genus at most $g$ that require $\Omega(\frac{g}{\log(g)})$-colours in any oriented colouring, before proving that every oriented graph with Euler genus at most $g$ has an oriented colouring using at most $O(g\log(g))$-colours.

GENA HAHN, Université de Montéal Resurrection -- revisiting old problems [PDF]

There are problems that themselves are perhaps rather unimportant but whose solutions require new approaches, new ideas, new theories. This talk is about three of these that have been haunting me for over twenty years. \begin{itemize} \item We invented the injective chromatic number in \cite{HSS} and there are now many papers on the subject. But one of the original questions, also asked in \cite{lin} in a different context, remains. \item The ultimate independence ratio of a graph has been studied extensively and much is known. Still, one of the problems from \cite{HHP} is still very much open. \item In \cite{manlove} the b-chromatic number of a graph is defined and questions answered. But in spite of sporadic results, not much is known. \end{itemize} \noindent{\bf Bonus} A problem I recently learnt from John Gimbel could fall in the same category, though we do not know, it is too young.

\begin{thebibliography}{99} \bibitem{HHP} G. Hahn, P. Hell, S. Poljak, {\it On the ultimate independence ratio}, European Journal of Combinatorics {\bf 16} (1995), 253 -- 261 \bibitem{HSS} G. Hahn, J. Kratochv\'{\i}l, D. Sotteau, J. \v{S}ir\'a\v{n}, On injective colourings, {\it Discrete Math. } {\bf 256} (2002), 179 -- 192. \bibitem{manlove} R. W. Irving, D. Manlove, The b-chromatic number of a graph, {\it Discrete Math.} {\bf 91} (1999), 127 -- 141. \bibitem{lin} N. Linial, R. Meshulam, M. Tarsi, Matroidal bijections between graphs, {\it J. Combin. Theory Ser. B} {\bf 45} (1988), 31 -- 44.

\end{thebibliography}

PENNY HAXELL, University of Waterloo A bounded diameter strengthening of K\H onig's Theorem [PDF]

K\H onig's theorem says that the vertex cover number of every bipartite graph is equal to its matching number. An equivalent formulation of K\H onig's theorem states that for every 2-colouring of the edges of a graph $G$, the vertex set of $G$ can covered by a set of at most $\alpha(G)$ monochromatic components. Here $\alpha(G)$ denotes the independence number of $G$.

We strengthen K\H onig's theorem by proving the existence of a function $f$ such that the following holds. For every 2-colouring of the edges of a graph $G$, there exists a set of at most $\alpha(G)$ monochromatic subgraphs, each of diameter at most $f(\alpha)$, that covers the vertex set of $G$.

Joint work with Louis DeBiasio, Ant\'onio Gir{\~a}o and Maya Stein

EMILY HEATH, Cal Poly Pomona Proper Rainbow Saturation for Cliques [PDF]

Given a graph $H$, we say that a graph $G$ is properly rainbow $H$-saturated if there is a proper edge-coloring of $G$ which contains no rainbow copy of $H$, but adding any edge to $G$ makes such an edge-coloring impossible. The proper rainbow saturation number is the minimum number of edges in an $n$-vertex properly rainbow $H$-saturated graph. There are few graphs for which the proper rainbow saturation number is known asymptotically, including $P_4$ and $C_4$. In this talk, we will discuss new results for cliques, including determining the proper rainbow saturation number of $K_4$ asymptotically.

This is joint work with Dustin Baker, Enrique Gomez-Leos, Anastasia Halfpap, Ryan Martin, Joe Miller, Alex Parker, Hope Pungello, Coy Schwieder, and Nicholas Veldt.

JEANNETTE JANSSEN, Dalhousie University Orthogonal Colourings of Random Geometric Graphs [PDF]

An orthogonal colouring of a graph $G=(V,E)$ is an injective assignment $f:V\rightarrow [k]^2$ of a pair of colours to each vertex of $G$, so that each coordinate constitutes a proper colouring. So if $f(u)=(a,b)$, $f(v)=(a',b')$ and $u$ and $v$ are adjacent, then $a\not= a'$ and $b\not= b'$. Since $f$ is injective, every pair of colours occurs at most once on any vertex. We show results on the minimum number of colours needed for an orthogonal colouring of a regular type of grid graph, and use this to find orthogonal colourings of the random geometric graph $GR(n,r)$. In particular, we investigate for which choice of parameters we have that $GR(n,r)$ almost surely has an orthogonal colouring that uses every colour pair exactly once.

ANDREW LANE, University of Victoria Proper Rainbow Saturation for Trees [PDF]

Given a graph $H$, say that a graph $G$ is properly rainbow $H$-saturated if there exists a rainbow $H$-free proper edge-colouring of $G$, and, for any non-edge $e$ of $G$, every proper edge-colouring of $G+e$ contains a rainbow copy of $H$. The proper rainbow saturation number is the minimum number of edges in a properly rainbow $H$-saturated graph on $n$ vertices. This is a natural variant of the graph saturation problem based on the rainbow extremal number. In this talk, we will discuss results on the proper rainbow saturation number, including exact values and asymptotically tight bounds for several classes of graphs, with a particular focus on trees.

Joint work with Natasha Morrison.

BEN MOORE, Institute of Science and Technology Austria On powers of sparse graphs [PDF]

It is conjectured that if C is a class of graphs with structurally bounded expansion, then even if we do not know the underlying transduction and bounded expansion class, we can solve all first order logic problems in polynomial time on C.

A simple class of graphs with structurally bounded expansion is d-powers of minor closed classes. I'll discuss some results on this class of graphs, in particular:

1) It is NP-complete to decide if a graph G has a square root H such that H is from a minor closed class M, so long as M contains at least 6 apex vertices

2) There exists an algorithm to 2-approximate the subchromatic number of bounded layered cliquewidth (which includes powers of planar graphs)

3) The subchromatic number of squares of planar graphs is at most 43

This is joint work with subsets of: Zdenek Dvorak and Abhiruk Lahari; Pankaj Kumar, Patrice Ossona de Mendez,Pedro Cortez, and Daniel Quiorz.

JOSHUA NEVIN, University of Ottawa Distant 2-Colored Components on Embeddings [PDF]

In this talk, we present a new result which consists of the following generalization of Thomassen's 5-choosability theorem: Let $G$ be a finite graph embedded on a surface of genus $g$. Then $G$ can be $L$-colored, where $L$ is a list-assignment for $G$ in which every vertex has a 5-list except for a collection of pairwise far-apart components, each precolored with an ordinary 2-coloring, as long as the face-width of $G$ is $2^{\Omega(g)}$ and the precolored components are of distance $2^{\Omega(g)}$ apart. This provides an affirmative answer to a generalized version of a conjecture of Thomassen and also generalizes a result from 2017 of Dvo\v{r}\'ak, Lidick\'y, Mohar, and Postle about distant precolored vertices.

JOZSEF SOLYMOSI, University of British Columbia A sparse removal lemma for pentagons [PDF]

Counting pentagons in graphs and hypergraphs is a classical problem in extremal graph theory. The following basic question has equivalent formulations using graphs or 3-uniform linear hypergraphs. Here, we use the hypergraph notation to state our main result. A 3-uniform hypergraph is linear if any two edges have at most one vertex common. A $C_5$ in a triple system is a set of ten distinct vertices $\{u_1, \ldots, u_5, v_1, \ldots, v_5\}$ and five (distinct) edges $u_iu_{i+1}v_i$ where $i \in [5]$ and indices are taken modulo 5. We say that this $C_5$ is an expansion of $u_1\ldots u_5$. Given a hypergraph $H$, write $e(H)$ and $d(H)$ for the number of edges and average degree of $H$, respectively.

Let $n>10$ and let $H$ be an $n$-vertex linear triple system with $m > 100 \, n^{3/2}$ edges. Then the number of copies of $C_5$ in $H$ is at least $m^6/n^7$.

This result has interesting applications in additive combinatorics and discrete geometry. Joint work with Dhruv Mubayi.

top of page