Graph colouring via entropy compression

Project: Research

Project Details

Project Description

Graphs and hypergraphs are mathematical structures that model networks. Colouring graphs and hypergraphs is a key problem in many fields including scheduling, computing derivatives, cryptography, and coding theory. This project will apply a revolutionary method called 'entropy compression' to produce new mathematical tools and algorithms for colouring graphs and hypergraphs. These results will have significant ramifications for the above applications, and will also be of fundamental importance in graph theory itself.
StatusFinished
Effective start/end date2/01/1431/12/17

Funding

  • Australian Research Council (ARC): AUD672,240.00
  • Australian Research Council (ARC): AUD48,970.00