Variations on the graph colouring problem

Jury

• Nadia Brauner, Professor, G-SCOP, Université Grenoble Alpes (chair)
• Daniel Cranston, Professor, College of William & Mary (USA) (reviewer)
• Paul Dorbec, Professor, GREYC, Université de Caen Normandie (reviewer)
• Daniel Gonçalves, CNRS researcher, LIRMMLaboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier, Université Montpellier 2 (examiner)
• Cléophée Robin, Associate Professor, IRIF, Université Paris Cité (examiner)

Abstract

The proper colouring problem is a fundamental topic in graph theory; not only do proper colourings exhibit a fascinating complexity as combinatorial objects, but they also feature in a wide array of applications, especially among resource allocation problems. However, some specific applications may require slightly different formulations of the proper colouring problem via the addition or relaxation of constraints. This thesis investigates the extremal aspects of three variations on the proper colouring problem by determining general bounds on the size of optimal solutions and identifying the structure of graphs in the limit cases.

The first chapter explores a generalisation of proper colouring through multichromatic constraints. A pattern is a graph with coloured vertices. Given a family P of patterns, a P-avoiding colouring of a graph G is a vertex colouring of G such that no pattern of P appears as a coloured subgraph in G (up to renaming the colours). The notion of proper colouring is retrieved with P consisting of the monochromatic edge, and many well-studied variants of proper colouring can be described and unified in this framework; we consider in particular frugal colouring and acyclic colouring. Studying the behaviour of the chromatic number in bounded-degree graphs excluding some subgraph has long been an active research topic; we extend this study to the more general notion of pattern-avoiding chromatic numbers by obtaining extremal bounds in terms of the maximum degree and the forbidden subgraphs.

The second chapter examines the notion or proper “conflict-free” colouring, which further requires that every open neighbourhood contains at least one solitary colour. Caro et al. conjectured that every connected graph of maximum degree ∆ ≥ 3 has a proper conflict-free colouring with ∆+1 colours. Liu and Reed proved this conjecture asymptotically by showing that ∆ + O(∆^{2/3} log∆) colours suffice. We improve this upper bound by showing that only ∆ + O(log ∆) colours suffice. Our method extends to the more general notion of proper h-conflict-free colouring (h ≥ 1), which constitutes a smooth interpolation between proper colouring and distance-2 colouring. We also consider the notion of conflict-free colouring of hypergraphs, for which we prove a Reed-type bound under the assumption that the hypergraph has no dense neighbourhood when restricted to edges of size 2.

The third chapter is dedicated to the notion of dominating colouring, where colour classes are dominating sets and we ask to maximize the number of colours used; the maximum is known as the domatic number. It is easy to observe that if G has minimum degree δ, then G has domatic number at most δ+1. We say that a class of graphs is dom-bounded if there exists a nondecreasing unbounded function f such that every graph G in said class has domatic number at least f(δ(G)). Zelinka showed that the class of all graphs is not dom-bounded, thus we are interested in identifying natural classes of graphs which are dom-bounded. By analogy with a conjecture of Gyárfás (1975) and Sumner (1981), we conjecture that the class of induced-H-free graphs is dom-bounded whenever H is a tree of diameter at most 3. We prove our conjecture for the case of stars and the 4-vertex path, leaving only the case of double stars open. We also consider the fractional relaxation of the domatic number problem; answering a conjecture of Gadouleau et. al in a strong form, we show that all connected graphs of minimum degree 2 with at least 8 vertices have fractional domatic number at least 5/2, which is tight even for graphs of large girth.