12. – 17. Juni 2016, Dagstuhl-Seminar 16241

Graph Polynomials: Towards a Comparative Theory


Jo Ellis-Monaghan (Saint Michael's College – Colchester, US)
Andrew Goodall (Charles University – Prague, CZ)
Johann A. Makowsky (Technion – Haifa, IL)
Iain Moffatt (Royal Holloway University of London, GB)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Report, Volume 6, Issue 6 Dagstuhl Report
Dagstuhl's Impact: Dokumente verfügbar
Programm des Dagstuhl-Seminars [pdf]


The intent of this 5-day Seminar was to develop a general theory of graph polynomials. Graph polynomials have played a key role in combinatorics and its applications, having effected breakthroughs in conceptual understanding and brought together different strands of scientific thought. The characteristic and matching polynomials advanced graph-theoretical techniques in chemistry; the Tutte polynomial married combinatorics and statistical physics, and helped resolve long-standing problems in knot theory. The area of graph polynomials is incredibly active, with new applications and new graph polynomials being discovered each year. However, the resulting plethora of techniques and results now urgently requires synthesis. Beyond catalogues and classifications we need a comparative theory.

There is a long history in this area of results in one field leading to breakthroughs in another when techniques are transferred, and this Seminar leveraged that paradigm. More critically, experts in the field have recently begun noticing strong resonances in both results and proof techniques among the various polynomials. The species and genera of graph polynomials are diverse, but there are strong interconnections: the Seminar initiated work on creating a general theory that will bring them together under one family. The process of developing such a theory of graph polynomials should expose deeper connections, giving great impetus to both theory and applications. This has immense and exciting potential for all those fields of science where combinatorial information needs to be extracted and interpreted.

The Seminar provided conditions ripe for cross-fertilization of ideas among researchers in graph theory and topological graph theory, in logic and finite model theory, and in current biocomputing and statistical mechanics applications. During the Seminar the participants were offered a conspectus of the broad area of graph polynomials. The view was confirmed that a synthetic approach is needed in order to see the wood for the trees. The discussions and collaborations initiated at the workshop promise well for the development of a unified theory of graph polynomials. This Seminar represented a convincing beginning, and, hopefully, similar meetings in future will further the envisaged project.

In the light of our stated goals, the Seminar provided ample time for discussion groups and tutorials. The participants (44) of the Seminar included some of the leading experts in combinatorics, knot theory, matroid theory and graph polynomials from Europe, the Americas, Asia and Australia. The composition of participants was both age and gender balanced with a quarter of the participants being women. The younger researchers (more than a quarter of the participants) profited from intense contacts and discussions with their more experienced colleagues. An inspiring problem session brought about particular directions for further research.

Summary text license
  Creative Commons BY 3.0 Unported license
  Jo Ellis-Monaghan, Andrew Goodall, Johann A. Makowsky, and Iain Moffatt

Related Dagstuhl-Seminar


  • Bioinformatics
  • Data Structures / Algorithms / Complexity
  • Verification / Logic


  • Graph Polynomials
  • Second Order Logic
  • Graph Colourings
  • Graph Homomorphisms
  • Graph Invariants
  • Matroid Invariants
  • Counting Functions
  • Complexity
  • Topological Graph Theory


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.