Graph theory studies mathematical structures called graphs, and their properties. A graph is a structure that consists of entities (usually called vertices or nodes) and the possible connections (usually called edges or links) between these entities. In some problems the directions of the links is important, for such problems the corresponding networks used to model the problem are called digraphs (directed graphs). This school aims to give a structured in-depth introduction to some active research areas within Graph Theory.

Our Objective

To raise awareness of some different areas of research in Graph Theory. To systematically introduce these areas to the participants and to make known some unsolved research questions in each areas. To provide a forum for participants to interact and initiate collaboration on areas they find interesting. To provide early career academics and graduate students an opportunity to explore different areas of research within Graph theory.

Abstracts [PDF]

Some Aspects of Semi-Transitively Orientable Graphs Zoom

By Professor Sergey kitaev, University of Strathclyde Glasgow, UK School on Graph Theory , 03 October 2022, 15h00 GMT+2 - Johannesburg.

An orientation of a graph is semi-transitive if it is acyclic, and for any directed path v_0 -> v_1 -> … -> v_k either there is no edge between v_0 and v_k, or v_i -> v_j is an edge for all 0 <= i < j <=k. Semi-transitive graphs generalize several important classes of graphs (such as 3-colorable, subcubic, circle and comparability graphs) and they are precisely the class of word-representable graphs studied extensively in the literature. Not all graphs are semi-transitive, and recognizing semi-transitivity is an NP-complete problem. In this lecture, I will go over some basics of the theory of semi-transitive graphs, and will introduce several open problems/research directions.

Some Aspects of Dominations in Graph Zoom

By Professor Michael Henning, University of Johannesburg, South Africa School on Graph Theory , 04 October 2022, 15h00 GMT+2 - Johannesburg.

Domination theory in graphs is a branch of graph theory that deals with structural properties of graphs. A dominating set of a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S, where two vertices are neighbors if they are adjacent. The domination number of G is the minimum cardinality of a dominating set.

In this lecture, we present an introduction to domination theory in graphs. We focus on the three core domination parameters, namely the domination number, the independent domination number, and the total domination number.

We establish properties of minimal dominating sets, and discuss bounds obtained on the core domination parameters in terms of the order, size, maximum degree, and minimum degree of the graph. We investigate relationships between the core domination parameters.

Some Aspects of Probabilistic Graph Theory Zoom

By Professor Paul Horn, University of Denver, USA School on Graph Theory , 05 October 2022, 15h00 GMT+2 - Johannesburg.

Starting with the pioneering work of Erdos, the probabilistic method has grown into one of the most important tools in modern graph theory. Probability gives a (typically non-constructive way) of both showing the existence of substructures within given graphs (eg. colorings, small dominating sets, subgraphs) and also showing the existence of graphs with surprising properties. In this lecture we’ll illustrate how some fairly simple probabilistic ideas (mostly expectation and concentration of measure) can be used to shed light in several areas of graph theory while hinting at some of the areas in which one can go deeper.

Some Aspects of Digraphs (Directed Graphs) Zoom

By Professor Gregory Gutin Royal Holloway, University of London, UK & Mr. Yacong Zhou, Royal Holloway, University of London, UK School on Graph Theory , 06 October 2022, 15h00 GMT+2 - Johannesburg.

The study of directed paths and cycles is one of the key areas of directed graph theory with many important results proved over years and many open questions still unsolved. We will consider some basic and recent results on directed paths and cycles in tournaments, generalizations of tournaments and digraphs. The results will be on both long and short paths and cycles.