Live Poster Session: Zoom Link
Thursday, July 30th 1:15-2:30pm EDT
Abstract: The Albertson Conjecture, formulated in 2008 and as yet proven only for n <= 16, states that if the chromatic number of a graph is at least n, then its crossing number is at least the crossing number of K_n, the complete graph with n vertices. Previous work on the Albertson conjecture has led to a related question: how exactly does the crossing number of a graph G compare to the crossing number of its “cone” CG constructed by addition of an ‘apex’ vertex, which increases the chromatic number by exactly 1? It is trivial that cr(CG) – cr(G) has no maximum value, but it is not obvious how we might calculate the minimal value of this difference as a function of cr(G). Previous work gave minimum values this difference can take for cr(G) < 6, and gave loose bounds on the asymptotic behavior of that minimal value. I extend these prior results by finding the exact minimum for cr(G) = 6. Further, the previous proof was reorganized to streamline the flow of ideas. Working through higher cases such as cr(G) = 7 in a similar manner could lead to the development of a formula for the general case of an arbitrary number of crossings, and the development of such a formula would help in understanding the Albertson Conjecture.
20200727_Poster-Sam-BidwellLive Poster Session: Zoom Link
Thursday, July 30th 1:15-2:30pm EDT