The Albertson Conjecture, formulated in 2008 and as yet proven only for n ≤ 18, 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, an operation 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). Alfaro et al. gave minimum values this difference can take for cr(G) < 6, and gave bounds on the asymptotic behavior of that minimal value. We extend these prior results by finding the exact minimum for cr(G) = 6 and cr(G) = 7. Further, we reorganize the proofs of the lower cases so that all proofs would use similar counting arguments and the same naming scheme for variables and concepts, to emphasize the similarity in the arguments used. Extending this argument to higher cases such as cr(G) = 8 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.
"},{"label":"Degree","value":["Bachelor of Arts with Departmental Honors"]},{"label":"Author-supplied Keywords","value":["Crossing number","Cone of a graph","Albertson conjecture"]},{"label":"Administrative Note","value":"Drupal Node ID: 23729