Come Hear CS Students talk about their Internship and Research!

Graph Theory and the Barnette Conjecture

John Key and Therese Relucio

David W. Barnette conjectured that the vertices of certain planar graphs can be traversed in a cycle along their edges. 50 years later and the conjecture is still unproven. Continuing off of last summer’s students’ research, we coded the conjecture as a SAT solution so that a solver could find a cycle on 1000 vertices in under 10 seconds. We then considered the graph of all disjoint cycle coverings of Barnette’s planar graphs and studied its structure. We finished the summer by writing algorithms that were designed to find such a cycle in the graph, which if proven to work without error, would prove the conjecture. Further research includes refining the algorithms and proving their steps.

Dial-In Information

Friday, September 18 at 3:30pm to 4:30pm

Virtual Event
Event Type

Lectures & Presentations

Target Audience

Students, Faculty & Staff



Computer Science

#CS Presentation

Google Calendar iCal Outlook

Recent Activity