Thesis topic

Computer assisted conjectures and proofs in extremal graph theory

  • Type
  • Keywords
    Extremal graph theory, computer assisted conjectures and proofs, discovery systems, graph invariants, graph transformations


The Algorithms Lab is specialized in the development of discovery systems in the context of extremal graph theory. The developed softwares are useful to generate conjectures but also to help to find proofs. In particular, proofs by graph transformations are conceived interactively or automatically. A postdoctoral project is possible either to develop such systems or on a theoretical level. Indeed, various conjectures expressed as bounds on graph invariants were or are generated. A postdoctoral subject can be defined by selecting one or several graph invariants about which some lower or upper bounds are open problems. For example, we study the number of nonequivalent colorings of a graph and the eccentric connectivity index of a graph.

About this topic

Related to
Algorithms Laboratory
Hadrien Mélot

Contact us for more info