http://www.dagstuhl.de/16241

### June 12 – 17 , 2016, Dagstuhl Seminar 16241

# Graph Polynomials: Towards a Comparative Theory

## Organizers

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)

## For support, please contact

## Documents

Dagstuhl Report, Volume 6, Issue 6

Aims & Scope

List of Participants

Shared Documents

Dagstuhl's Impact: Documents available

Dagstuhl Seminar Schedule [pdf]

## Summary

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.

**License**

Creative Commons BY 3.0 Unported license

Jo Ellis-Monaghan, Andrew Goodall, Johann A. Makowsky, and Iain Moffatt

## Classification

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

## Keywords

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