Programme
| Monday | Tuesday | Wednesday | Thursday | Friday | |
|---|---|---|---|---|---|
| 9:00 - 9:30 | Arrival | Set-defined graph classes and chi-boundedness (Viktor Zamaraev) | Bounding bandwidth (Maria Chudnovsky) | Graph Searches - Structure and Algorithms (Ekkehard Köhler) | Work in groups |
| 9:30 - 10:00 | Open problem session | Set-defined graph classes and chi-boundedness (Viktor Zamaraev) | Bounding bandwidth (Maria Chudnovsky) | Graph Searches - Structure and Algorithms (Ekkehard Köhler) | Work in groups |
| 10:00 - 10:30 | Open problem session | Short progress report | Short progress report | Short progress report | Work in groups |
| 10:30 - 11:00 | Coffee Break | Coffee Break | Coffee Break | Coffee Break | Coffee Break |
| 11:00 - 12:30 | Open problem session | Work in groups | Work in groups | Work in groups | Work in groups |
| 12:30 - 13:30 | Lunch Break | Lunch Break | Lunch Break | Lunch Break | Lunch Break |
| 13:30 - 15:00 | Work in groups | Work in groups | Work in groups | Work in groups | Work in groups |
| 15:00 - 15:30 | Coffee Break and Group Photo | Coffee Break | Coffee Break | Coffee Break | Coffee Break |
| 15:30 - 17:00 | Work in groups | Work in groups | Work in groups | Work in groups | Final progress report |
| 19:00 - … | Conference dinner at Restavracija Kamin |
Talk Abstracts
TITLE: Set-defined graph classes and chi-boundedness (Viktor Zamaraev)
ABSTRACT:
We study set-defined graph classes: hereditary classes of graphs in which vertices are assigned fixed-length numerical tuples and adjacency depends only on equality patterns among tuple coordinates. These classes arise naturally in structural graph theory, communication complexity, logic, and adjacency labelling schemes. We investigate the structural complexity of set-defined classes by asking when they are $\chi$-bounded, i.e., when chromatic number is controlled by clique number throughout the class.
Our main results give structural and algorithmic characterizations of $\chi$-boundedness in set-defined classes. First, we establish a decomposition theorem showing that every graph in a set-defined class can be partitioned into a number of parts bounded polynomially in its clique number, so that each part induces the union of a constant number of shift-colorable graphs, that is, graphs admitting a homomorphism to a shift graph. This identifies bounded unions of shift-colorable graphs as the fundamental obstruction to $\chi$-boundedness in set-defined classes.
Second, for full set-defined graph classes, that is, classes containing all graphs realizable by a fixed Boolean rule on equality patterns, we prove a stronger dichotomy: every such class is either polynomially $\chi$-bounded or contains shift graphs of arbitrarily large chromatic number. Moreover, we provide an algorithm that, given a Boolean-function description of a full set-defined class, decides $\chi$-boundedness of the class.
We discuss the implications of these results for the Gyárfás–Sumner conjecture, the Erdős–Hajnal problem on subgraphs of large girth and large chromatic number, and several related open problems.
Based on joint work with Sarosh Adenwalla, Samuel Braunfeld, Tomáš Hons, and John Sylvester.
TITLE: Bounding bandwidth (Maria Chudnovsky)
ABSTRACT:
Given an ordering of the vertices of a graph G, its bandwidth is the maximum distance (in the ordering) between two adjacent vertices of G. The bandwidth of G is the minimum bandwidth of an ordering of the vertices of G.
What graphs have small bandwidth? Several examples of families of trees of unbounded bandwidth are known; and in 2014 Drego and Lokshtanov showed that every tree of high bandwidth contains as a subgraph a member of one of these families. In this talk we will extend this result to the class of all graphs, rather than just trees.
The proofs are algorithmic, and consequently we also get an FPT approximation algorithm for bandwidth.
This is joint work with Daniel Lokshtanov and Eran Nevo.
TITLE: Graph Searches - Structure and Algorithms (Ekkehard Köhler)
ABSTRACT:
Graph searches are the most basic algorithmic tools in graph theory. Everybody knows and uses breadth-first search (BFS) or depth-first search (DFS) for various applications and proofs. In spite of the frequent use of graph searches many of their structural properties are more complicated than it seems at first sight.
In this talk we consider various graph search algorithms and review different structural and algorithmic results on these searches. In particular, we discuss the end-vertex problem for different searches and fast implementations of lexicographic depth-first search (LexDFS).