TBA
In this talk, we will share two new problems about cages.
A cage is a regular graph with a given girth (the length of the shortest cycle) and the minimum number of vertices. The cage problem was posed in 1947 by Tutte, who asked about the minimum order of cubic graphs with fixed girth. The problem was later generalized to any degree, and in 1963, Erdős and Sachs proved their existence. Since then, this problem has been widely studied.
In this talk, Linda Lesniak will relate this problem to the chromatic number, which is the minimum number of colors needed to color the vertices of a graph so that no adjacent vertices share the same color. There is a conjecture stating that cages of even girth are bipartite. We ask about the existence of the smallest regular graphs with even girth that are not bipartite; that is, we consider regular graphs of even girth, chromatic number 3, and minimum order. More generally, given three parameters $r \geq 2$, $g \geq 3$, and $\chi \geq 3$ (degree, girth, and chromatic number), we ask for graphs of minimum order with these parameters, or the $(r,g;\chi)$-cages.
Also, in this talk, Gabriela Araujo introduces a new problem that she and György Kiss have studied very recently, about the existence and constructions of balanced biregular cages. They are bi-regular graphs (graphs with two degrees $r$ and $s$), but with the property that they have the same number of vertices of degree $r$ as vertices of degree $s$, and also with minimum order.
TBA
TBA
TBA
TBA