Yifan Zhu

Hui Song

Guanghui Yang

Lulu Fu

Yuting He

Junjie Feng

Jie Yang

Zengxian Hu

Guanlin Tian

Chuanyong He

Shao

Keywords: Graphes planaires extérieurs 2-connexes, Graphes sans triangle, DP-colorations, Colorations fractionnaire, Hamilton-connectivité, Some vertex colouring problems and a generalisation of Hamilton-connectivity 2-connected outerplanar graphs, Triangle-free graphs, DP-colourings, Fractional colourings

Certains problèmes de coloration des sommets et une généralisation de la Hamilton-connectivité dans des graphes

Hamilton-connectivity; Maximum degree; Degree sum.

Abstract:

The decomposition of graphs refers to the process of breaking down a complex graph into simpler, smaller components, often with the goal of analysing or solving problems related to the graph. It is an important tool to display the global structure and properties in a more fine-grained manner, and also useful in solving problems that involve finding specific structures in a graph.

There are several common types of graph decomposition techniques that are widely used in graph theory and related fields, including tree decomposition, block decomposition, modular decomposition, hierarchical decomposition, etc. This thesis studies two kinds of vertex decomposition of a graph:

proper colourings (decomposition into independent sets) and Hamilton-connectivity (decomposition into internally-disjoint paths between two sets where the paths cover all the vertices of graphs).

Acknowledgement

First, I would like to express my sincere gratitude to my supervisor, Prof. Hao

Li, for his guidance, support, and encouragement throughout my doctoral research.

In the past four years, I have been fortunate to have Prof. Li as my academic advisor, who not only imparted invaluable knowledge on research methodologies but also extended generous support in my personal life. Prof. Li instructed me on various aspects of research, including how to find problems, how to consider problems, how to give a presentation and more. When I was sick, Prof. Li took me to the hospital and helped me understand the French medical system. I am also very grateful to his wife, who often invited me to their home as a guest and cooked Chinese food for me so that I would not get homesick. During the unprecedented COVID-19 pandemic, Prof. Li exhibited genuine concern for our safety and well-being by regularly checking up on us and offering assistance. I am immensely grateful for Prof. Li's unwavering guidance and support throughout my doctoral journey.

I would like to thank Prof. François Pirot, for introducing me to the fascinating random colouring process, for successfully sharing his passion with me, for generously guiding and supporting me during my studies, and for being patient and encouraging with this slow-witted student. Whenever I had any academic questions, I could always walk into his office and ask him. He would immediately put aside his work on hand to discuss it with me. François always encourages me to face challenges with confidence. He says it's because he believes I can do it. Whenever I faced any obstacles in my research, his astute suggestions helped me to navigate through them successfully.

I express my sincere gratitude to my reading committee for dedicating their time to thoroughly review the entire content of my thesis and providing me with valuable feedback. I also appreciate the presence of each member of my jury at my defence, which is an honour to me.

I am grateful for my fruitful collaborations with Yannis Manoussakis (+RIP),

ii Qiancheng Ouyang, Shuni-chi Maezawa, Jie Hu, Zengxian Tian, Yue Ma and of course again Hao and François. Without them, I would have walked a rather lonely path in my field.

I would like to thank Prof. Guanghui Wang, my master's supervisor, for introducing me to the field of graph colouring, for successfully sharing his passion with me, and for being very supportive all those years. Thanks to Prof. Bing Yao who introduced us to the many wonders of graph theory.

I am grateful to Prof. Yue Ma for introducing me to the applications of graph theory and exploring the mysteries of semantics together. I especially thank the guys from GaLac for the fun discussions during lunch. Thank LISN for providing me with everything that I needed in order to perform my research in excellent conditions.

I would like to extend my appreciation to my colleagues and friends, Linlin

List of Figures L , M 2 L , respectively. The number of matching assignments between L(u) and L(v) (resp. L(v) and L(w)) is two (resp. three) and so the multiplicity of uv (resp. vw) is two (resp. three) in G m . Dans le deuxième chapitre, nous contribuons aux extensions des colorations de sommets dans les graphes planaires. Les colorations par liste sont une généralisation des colorations propres, où chaque sommet choisit sa couleur dans une liste privée de couleurs autorisées [START_REF] Jensen | Graph coloring problems[END_REF]. En 2008, Hutchinson [START_REF] Hutchinson | On list-coloring outerplanar graphs[END_REF] a étudié le problème d'extension d'un problème de coloration de degré-liste sur des graphes planaires extérieurs. Elle a montré que si un graphe planaire extérieur biparti 2-connexe G a une liste de couleurs L(v) pour chaque sommet v avec |L(v)| ≥ min{deg G (v), 4}, alors G est L-colorable ; et si un graphe extérieur biparti maximal G avec au moins quatre sommets a une liste de couleurs L(v)

The left graph is a part of the (M

L ∪ M 1 L ∪ M 2 L )-cover. The right graph is a part of the (M L ′ ∪ M 1 L ′ ∪ M 2 L ′ )-
pour chaque sommet v avec |L(v)| ≥ min{deg G (v), 5}, alors G est L-colorable.
Elle a également montré que les bornes inférieures sont optimales au sens où la borne inférieure 4 pour les graphes planaires extérieurs bipartis 2-connexes (resp.

5 pour les graphes planaires extérieurs maximaux) ne peuvent pas être remplacées par 3 (resp. 4). Nous visons à déterminer si ces bornes sont valables pour les DP-colorations, une généralisation des colorations par liste. Les DP-colorations ont été introduites par Dvořák et Postle [START_REF] Dvořák | Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8[END_REF] pour résoudre une conjecture sur les colorations par liste. Une fois qu'elles ont été proposées, elles ont attiré l'attention de nombreux chercheurs. Il y a une quantité significative de recherches visant à étendre les résultats des colorations par liste aux DP-colorations. Nos résultats indiquent que la première borne des résultats de Hutchinson n'est pas suffisante pour les DP-colorations. Cependant, la deuxième borne est suffisante pour tous les graphes planaires extérieurs 2-connexes.

Dans le troisième chapitre, nous nous intéressons aux colorations fractionnaires des graphes sans triangles avec un degré maximal au plus d, en mettant l'accent sur le cas d = 4. Nous désignons par χ f (d, K 3 ) le supremum du nombre chromatique fractionnaire sur tous les graphes sans K 3 avec un degré maximal au plus d. Il a été établi par Dvořák, Sereni et Volec [START_REF] Dvořák | Subcubic triangle-free graphs have fractional chromatic number at most 14/5[END_REF] que χ f (3, K 3 ) = 14 5 . Pour d ∈ [START_REF] Borodin | Problems of colouring and of covering the vertex set of a graph by induced subgraphs[END_REF] \ {3}, il existe une borne supérieure χ f (d, K 3 ) ≤ d+3 2 , qui découle de la borne fractionnaire de Reed, établie par Molloy et Reed [START_REF] Molloy | Graph colouring and the probabilistic method[END_REF]. On pense que cette borne n'est pas optimale pour tout d ≥ 3. Pour d ≥ 17, Pirot et Sereni [START_REF] Pirot | Fractional chromatic number, maximum degree, and girth[END_REF] ont utilisé des distributions hardcore sur les ensembles indépendants des graphes sans triangles pour obtenir les meilleures bornes supérieures connues pour χ f (d, K 3 ). Dans le cas d = 4, Jones [START_REF] Jones | Independence in graphs with maximum degree four[END_REF] a prouvé que pour tout graphe sans triangle G de degré maximal 4 avec n sommets, la taille des ensembles indépendants maximum est au moins 4n 13 . Cela implique que χ f (4, K 3 ) ≤ 13 4 si nous restreignons sa définition à la classe des graphes vertex-transitifs. En général, χ f (4, K 3 ) se situe entre 3.25 et 3.5 (selon la borne fractionnaire de Reed). Nous utilisons la méthodologie introduite par Pirot et Sereni [START_REF] Pirot | Fractional chromatic number, maximum degree, and girth[END_REF] en utilisant des distributions de probabilités mixtes afin de prouver que χ f (4, K 3 ) < 3.4663.

Dans le quatrième chapitre, nous étudions une généralisation des problèmes de connexion Hamiltonienne. Un graphe G est k-fan-connexe si pour chaque sommet v ∈ V (G) et chaque sous-ensemble de sommets U = {u 1 , u 2 , . . . , u k } de V (G) \ {v}, il existe un ensemble de chemins internement disjoints P 1 , P 2 , . . . , P k tels que P i est un chemin reliant v et u i pour 1 ≤ i ≤ k et ces chemins couvrent tous les sommets de G. Cette notion a été introduite pour la première fois par Lin, Tan, Hsu et Hsu [START_REF] Lin | On the spanning fan-connectivity of graphs[END_REF], qui est un concept de type Menger similaire à la connectivité englobante d'un graphe. Récemment, il y a eu un intérêt pour l'étude des conditions suffisantes pour les graphes k-fan-connexes. Inspirés par cette définition, nous proposons les graphes (k 1 , k 2 )-Hamilton-connexes. Un graphe G est appelé (k 1 , k 2 )-Hamilton-connexe, si pour tout deux sous-ensembles disjoints de sommets X = {x 1 , x 2 , . . . , tree decomposition, block decomposition, modular decomposition, hierarchical decomposition, etc. This thesis studies two kinds of vertex decomposition of a graph: proper colourings (decomposition into independent sets) and Hamilton-connectivity (decomposition into internally-disjoint paths between two sets where the paths cover all the vertices of graphs).

x k 1 } et U = {u 1 , u 2 , . . . , u k 2 }, il existe k 1 k 2 chemins internement disjoints reliant x i à u j pour 1 ≤ i ≤ k 1 et 1 ≤ j ≤ k 2 ,
In the second chapter, we contribute to extensions of vertex colourings in planar graphs. List colourings are a generalisation of proper colourings, where every vertex picks its colour from a private list of allowed ones [START_REF] Jensen | Graph coloring problems[END_REF]. In 2008, Hutchinson [START_REF] Hutchinson | On list-coloring outerplanar graphs[END_REF] studied a degree-choosability problem on outerplanar graphs. She showed that if a 2-connected bipartite outerplanar graph G has a list of colours

L(v) for each vertex v with |L(v)| ≥ min{deg G (v), 4}, then G is L-colourable;
and if a maximal outerplanar graph G with at least four vertices has a list of colours

L(v) for each vertex v with |L(v)| ≥ min{deg G (v), 5}, then G is L-colourable.
She also showed the lower bounds are sharp in the sense that the lower bound 4 for 2-connected bipartite outerplanar graphs (resp. 5 for maximal outerplanar graph) cannot be replaced by 3 (resp. 4). We aim to determine whether these bounds hold for DP-colourings, a generalisation of list colourings. DP-colourings were introduced by Dvořák and Postle [START_REF] Dvořák | Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8[END_REF] to solve a conjecture about list colourings.

Once they were put forward, they caught the attention of many researchers. There is a significant amount of research to extend the results of list colourings to DP-colourings. Our findings indicate that the first bound of Hutchinson's results is not sufficient for DP-colourings. However, the second bound is sufficient for all 2-connected outerplanar graphs.

In the third chapter, we are interested in fractional colourings of triangle-free graphs of maximum degree at most d with a specific focus on the case d = 4.

We denote χ f (d, K 3 ) the supremum of the fractional chromatic number over all K 3 -free graphs of maximum degree at most d. It has been settled by Dvořák, Sereni, and Volec [START_REF] Dvořák | Subcubic triangle-free graphs have fractional chromatic number at most 14/5[END_REF]

that χ f (3, K 3 ) = 14/5. For d ∈ [16] \ {3}, there is an upper bound χ f (d, K 3 ) ≤ d+3
2 , which follows from the fractional Reed bound, established by Molloy and Reed [START_REF] Molloy | Graph colouring and the probabilistic method[END_REF]. It is believed that this bound is not tight for any d ≥ 3. For d ≥ 17, Pirot and Sereni [START_REF] Pirot | Fractional chromatic number, maximum degree, and girth[END_REF] have used hard-core distributions on the independent sets of triangle-free graphs in order to derive the best-known upper bounds for χ f (d, K 3 ). For the case d = 4, Jones [START_REF] Jones | Independence in graphs with maximum degree four[END_REF] proved that for every triangle-free graph G of maximum degree 4 on n vertices, the size of maximum independent sets is at least 4n 13 . This implies that χ f (4, K 3 ) ≤ 13 4 if we restrict its definition to the class of vertex-transitive graphs. In general, χ f (4, K 3 ) lies between 3.25 and 3.5 (by the fractional Reed bound). We use the methodology introduced by Pirot and Sereni [START_REF] Pirot | Fractional chromatic number, maximum degree, and girth[END_REF] together with mixed probability distributions in order to prove that χ f (4, K 3 ) < 3.4663.

In the fourth chapter, we investigate a generalisation of Hamilton-connected

problems. A graph G is k-fan-connected if for every vertex v ∈ V (G) and every vertex subset U = {u 1 , u 2 , . . . , u k } of V (G) \ {v},
there is a set of internally-disjoint paths P 1 , P 2 , . . . , P k such that P i is a path connecting v and u i for 1 ≤ i ≤ k and these paths cover all the vertices of G. This notion was first introduced by Lin, Tan, Hsu, and Hsu [START_REF] Lin | On the spanning fan-connectivity of graphs[END_REF], which is a Menger-type concept similar to the spanning connectivity of a graph. Recently, there has been an interest in studying the sufficient conditions for k-fan-connected graphs. Inspired by this definition, we propose

(k 1 , k 2 )-Hamilton-connected graphs. A graph G is called (k 1 , k 2 )-Hamilton-connected, if for any two disjoint vertex subsets X = {x 1 , x 2 , . . . , x k 1 } and U = {u 1 , u 2 , . . . , u k 2 }, there are k 1 k 2 internally-disjoint paths connecting x i to u j for 1 ≤ i ≤ k 1 and 1 ≤ j ≤ k 2 , which cover all the vertices of G. It is obvious that (1, k 2 )-Hamilton-connectedness is equivalent to k 2 -fan connectedness. Let σ 2 (G) be the minimum value of deg(u) + deg(v) over all pairs {u, v} of non-adjacent vertices in G. We prove that an n-vertex graph G is (2, k)-Hamilton-connected if G is (5k -4)-connected with σ 2 (G) ≥ n + k -2
where k ≥ 2. We also prove that if

σ 2 (G) ≥ n + k 1 k 2 -2 with k 1 , k 2 ≥ 2, then G is (k 1 , k 2 )-Hamilton-connected.
Moreover, we construct two graphs to show that our results are sharp.

We conclude this thesis in Chapter 5 and give some prospects.

-Introduction

Graphs are mathematical abstractions that represent any network that might possibly exist in the real world. The concept of graph theory started with the Königsberg Bridge's problem in 1735 for the first time in history [START_REF] Biggs | Graph Theory[END_REF]. It is related to various domains of mathematics, including algebra, topology, probabilities, and extremal combinatorics. For instance, Extremal Graph Theory focuses on finding graphs with extreme properties or determining bounds on certain graph parameters, and probabilistic graph theory investigates random processes on graphs, such as random walks. The probabilistic method is a technique for proving the existence of objects with specific properties by studying the typical behaviour of a random one.

Graph Theory is rich in many problems of practical and/or theoretical interest; among the most classical ones we can mention: Shortest Path Problem, Minimum Spanning Tree Problem, Eulerian Path (Cycle) Problem, Graph Isomorphism and Homomorphism, Graph Colouring Problem and Hamilton-connectivity Problem that we are interested in, and so on. On the other hand, graphs are extensively used in many disciplines. For example, we can non-exhaustively mention: anatomy (neural circuit), biology (protein interaction network), chemistry (crystal structures), computer sciences (web, peer-to-peer networks), artificial intelligence (artificial neural network), statistics (Bayesian network), electricity (electrical grid), telecom (telecommunication network), transportation (road network, rail network), and urbanism (gas network, water distribution network).

In this thesis, we mainly study some vertex colouring problems and a generalisation of Hamilton-connectivity in graphs. In addition to mathematics, the colouring problem has a remarkable range of applications in other fields of science. All those seemingly unrelated topics -the efficiency of a computer processor, wireless communication networks, the number of tracks required in a railway station, and the number of frequencies that our smartphones should be able to capture -depend on a colouring problem. Hamilton-connectivity also has many applications in different fields, including network design and fault tolerance, DNA sequencing, robotics and automated path planning, and circuit design.

We introduce the fundamentals of graph theory in the first section of this chapter to make it easier to describe the context of our research topic. In the second section, we present the background and main classic results on proper vertex colourings, including variants of the chromatic number. We introduce the background and some insightful findings that will be related to our studies on Hamilton-connectivity in the third section. The final section will describe the contributions of the thesis and the outline of the manuscript.

. The Basics

Graphs in this thesis are simple unless otherwise stated. We follow Bondy and Murty [START_REF] Bondy | Graph theory[END_REF] for undefined terms and notations in graph theory.

. Properties of planar graphs

A graph G is planar if G can be drawn in the plane with no pair of edges crossing. Such a drawing is called an embedding of G on the plane. Graphs already embedded on the plane are called plane graphs. Faces of a plane graph are regions bounded by a set of edges and which contain no other vertex or edge. The degree of a face f , denoted deg(f ), is the number of edges along its boundary.

Alternatively, it is the number of vertices along its boundary. Every edge in a planar graph is shared by exactly two faces.

In a plane graph, there is precisely one face that is unbounded; we call this the infinite, or outer face (sometimes one calls it external face), and all others are finite faces. An edge is called external (respectively, internal) when it lies (resp., does not lie) on the boundary of the external face.

A planar graph is called outerplanar if the graph can be embedded on the plane in such a way that all vertices of the graph lie on the outer face.

Planar graphs play an essential role in a variety of applications, making them an intriguing class of graphs to investigate. These graphs have specific properties that follow mainly from Euler's Formula, which establishes a relationship between the number of vertices, edges, and faces in a plane graph.

Theorem 1 (Euler's Formula) Let G be a connected plane graph on n vertices, m edges, and f faces. Then

n + f -m = 2.
There are many applications to this formula, the most notorious one being certainly the Discharging Method. Although we do not rely on it in this thesis, it is one of the most efficient tools to derive results on planar graphs. We will now deduce the following simple result from Euler's Formula.

Lemma 1 Every planar graph on n ≥ 3 vertices has at most 3n -6 edges.

Proof. Let G be a connected planar graph (otherwise we could add edges to make the graph connected). Let m be the number of edges and f be the number of faces of G. By Euler's Formula, we have

f = 2-n+m. A simple counting argument shows that i deg(f i ) = 2m
where {f i } i are the faces of G. Note that we count a bridge twice at every face with which they are incident. Since the number of edges in the boundary of each face is at least 3, we have f ≤ 2m 3 . Thus m ≤ 3n -6, as desired.

As we know, the sum of the degrees of the vertices of a graph is precisely twice the number of edges of that graph. Thus, it follows from Lemma 1 that any planar graph has average degree less than 6. In particular:

Corollary 1 Every planar graph has a vertex of degree at most 5.

The girth of G, denoted girth(G), is the size of a smallest cycle in G. More generally, the average degree of a planar graph is bounded by a decreasing function of its girth as follows.

Theorem 2 [START_REF] Pirot | Colouring sparse graphs[END_REF] The average degree of a planar graph of girth at least g is less than 2g g-2 .

Since being planar is a monotone property, it means that any subgraph of a planar graph is also planar. Hence the degeneracy of a planar graph is at most 5.

Theorem 3

For every planar graph G, δ * (G) ≤ 5, and if moreover G is triangle-free (and so of girth g ≥ 4),

δ * (G) ≤ 3.
Recall that a planar graph is said to be outerplanar if it has a planar drawing in which all vertices lie on the outer face. For each outerplanar graph, we can find a vertex of degree at most 2.

Lemma 2 Every edge-maximal outerplanar graph G on n ≥ 3 contains a vertex of degree 2. In particular, every outerplanar graph has a vertex of degree at most 2.

Proof. Let G be an edge-maximal outerplanar graph. We first claim that G is 2-connected. Toward a contradiction, suppose that G is not 2-connected. Let us take an outerplanar embedding of G. If G is not connected, then we could draw a non-crossing curve between any two vertices u and v in different components of G and still every vertex of G would be on the boundary of the outer face. So the graph G + uv would be outerplanar, which contradicts that G is edge-maximal. If the connectivity of G is 1, then let v be a cut-vertex and let C 1 and C 2 be two components in G -v. Let u 1 ∈ C 1 and u 2 ∈ C 2 be neighbours of v, such that the drawing of the edges u 1 v and vu 2 are leaving v right after each other when we go around v in a very small cycle. Two such neighbours certainly exist as v has neighbours both in C 1 and C 2 . Now it is possible to draw a non-crossing curve between u 1 and u 2 by following closely first the drawing of the edge u 1 v and then the drawing of the edge vu 2 . This curve will close a triangle with the curves u 1 v and vu 2 with no vertex in its interior, so the obtained drawing of G+u 1 u 2 is outerplanar, contradicting our assumption of G. Hence G is 2-connected.

If we consider any planar drawing of G in which all vertices lie on the outer face, the outer face is a cycle (without repeated vertices), and all internal faces are triangles. Indeed, we assume there exists a face f i and deg(f i ) > 3. We claim that there exist two non-adjacent vertices v j and v k of f i . Otherwise, the edge v j v k must be outside of f i ; it contradicts the outerplanarity of G. So we can add the edge v j v k to G without losing outerplanarity. It contradicts the maximality of G.

A chord is an edge between two non-consecutive vertices of a given cycle. We consider a shortest chord xy of the outer face, the distance of x and y on the outer face is at least 2 because G is simple. So any vertex between x and y on the shortest path from x to y on the outer face must have degree 2.

Since outerplanar graphs form a hereditary family, this implies that outerplanar graphs are 2-degenerate.

. Connectivity in graphs

The basic result in the theory of connectivity was proved by Menger in 1927.

Two s-t paths are independent if they have only the vertices s and t in common.

We also say that the two s-t paths are internally-disjoint paths.

Theorem 4 (Menger, 1927 [79]) 1. Let s and t be distinct nonadjacent vertices of a graph G. Then the minimal number of vertices separating s from t is equal to the maximal number of independent s-t paths.

2.

Let s and t be distinct vertices of G. Then the minimal number of edges separating s from t is equal to the maximal number of edge-disjoint s-t paths.

It is often the case that Menger's Theorem needs to be applied as another version, the following corollary. on computer analysis and verification, dealing with an exhaustive enumeration of numerous cases. The complexity of their proof sparked controversy, as some mathematicians were sceptical about the role of computers in mathematical proofs.

In addition to the computer-checked parts, it contains a part that needs to be checked by a lengthy manual case analysis, and the researchers trying to do so actually found flaws (though likely fixable ones). In 1997, the first universally accepted proof of Four Colour Theorem is the one by Robertson, Sanders, Seymour, and Thomas [START_REF] Robertson | The four-colour theorem[END_REF]. They announced another proof, still using a computer, but simpler than Appel and Haken's in several respects. However, to this date, mathematicians still continue to work on the Four Colour Theorem, aiming to find more intuitive and concise proofs that require less reliance on computer verification.

The Four Colour Theorem is just one of the many challenges in the field of graph colouring, which deals with finding the optimal way to colour the vertices of a graph so that no two adjacent vertices have the same colour -it is known as a proper colouring. The minimum number of colours required for a proper colouring of a graph is called its chromatic number, and the colouring problem is the process of determining the chromatic number of a given graph. Graph colouring has numerous applications across various fields. For example, graph colouring is used to schedule and assign time slots to events or activities in various domains such as schools, universities, conferences, and sports tournaments. Each event is represented as a vertex, and conflicts between events are represented as edges. By assigning distinct colours (time slots) to conflicting events, a conflict-free schedule can be generated.

However, the colouring problem is notoriously challenging, as it is NP-hard to solve or even approach with a non-optimal solution. This means that it is highly unlikely that we will be able to devise an effective method for determining the optimal colouring of any given graph. For this reason, a significant portion of graph colouring research focuses on finding large classes of graphs for which either the colouring problem is less difficult, or the chromatic number is substantially lower.

. Presentation and definition

We now introduce the definitions of some vertex colourings and their related basic properties.

Proper k-colourings

Definition 1. Let G be a graph.

1. A k-colouring of G is a function c : V (G) → [k] where [k] = {1, 2, . . . , k}.
This can be seen as a function which associates to every vertex v ∈ V (G) a colour among a palette of k possible ones. A partial colouring of G is a colouring of an induced subgraph of G.

2. A colouring c of G is proper if no two vertices of the same colour are adjacent;

∀uv ∈ E(G), c(u) ̸ = c(v).
When there exists a proper k-colouring of G, we say that G is k-colourable. A graph G is k-colourable if and only if it is a subgraph of the complete k-partite graph K k * n . In particular, the class of bipartite graphs is exactly the class of 2-colourable graphs. Being k-colourable is a hereditary property;

∀H ⊆ G, χ(H) ≤ χ(G).

There are many equivalent definitions of a proper k-colouring of a graph G.

Here, we present a definition based on a linear program. The chromatic number χ(G) of a graph G is naturally defined as the solution of an integer linear program with one variable w I for every of its independent sets I ∈ I (G).

χ(G) = min I∈I (G) w I , such that            w I ∈ {0, 1} for each I ∈ I (G) I∈I (G) v∈I w I ≥ 1 for each v ∈ V (G).
(1.1)

List colourings

To tackle some graph colouring problems, Vizing [START_REF] Vizing | Vertex colorings with given colors[END_REF], and independently Erdős, Rubin, and Taylor [START_REF] Erdős | Choosability in graphs[END_REF] introduced list colourings, a generalisation of proper colourings. In a k-colouring, each vertex picks a colour from a common set of colours [k]. Now we consider a generalisation of k-colourings to make each vertex choose its colour from a private list of allowed colours. These are list colourings.

Definition 2.

Let G be a graph.

1. A list assignment L with a graph G is a mapping that maps each vertex

v of G to a list of integers L(v). A list assignment L is called a t-list assignment if |L(v)| = t for every v ∈ V (G). A list assignment L is called a degree-list assignment if |L(v)| = deg G (v) for every v ∈ V (G). 2. A graph G is L-coloured if there exists a proper colouring c of G such that ∀v ∈ V (G), c(v) ∈ L(v). 3. A graph G is k-choosable if G is L-coloured for every k-list assignment L.
4. The choice number, or list chromatic number, is the minimum k such that

G is k-choosable. It is denoted χ ℓ (G).

5.

A graph G is said to be degree-choosable if G is L-coloured for every degree-list assignment L.

Remark 1. The graph G has a proper k-colouring if and only if G has an

L-colouring with L(v) = [k]. Hence we have ∀G, χ ℓ (G) ≥ χ(G).

DP-colourings

List colourings helped establish a number of proper colouring results; however, it is usually much more difficult to establish upper bounds on the choice number than on the chromatic number. The methods used in proper colourings may not directly apply to list colourings. For instance, the operation of identifying vertices, which is common in proper colourings, may not be feasible in list colourings. Let us illustrate this with an example of a proof of the Five Colour Theorem on planar graphs. We first observe that G contains a vertex v of degree at most 5. If Given a 5-colouring ϕ of G ′ , we then obtain a 5-colouring of G by giving both

x and y the colour ϕ(w) and choosing a colour for v distinct from the colours of its neighbours. But in list colourings, vertex identification as a strategy is impractical, since different vertices can have various lists of available colours in list colourings. To solve this issue, and allow themselves to use vertex identification in the context of list colourings, Dvořák and Postle [START_REF] Dvořák | Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8[END_REF] have introduced the notion of correspondence colourings (also referred to as DP-colourings).

As we all know, a proper k-colouring of G is isomorphic to a (maximum) independent set of size |V (G)| of the Cartesian product G2K k . List colourings are to find such an independent set in the setting of monochromatic matchings between two adjacent list assignments. While the idea behind correspondence colourings is to forbid more configurations, it is to find an independent set of size n(G) for any matched colours between two adjacent list assignments. The lists do not matter for correspondence colourings (as long as all vertices use the same number of colours). Note that when performing vertex identification for DP-colourings, it is in general necessary to preserve the parallel edges if they arise.

Here we present the definition of DP-colourings in simple graphs from Bernshteyn, Kostochka, Pron [START_REF] Bernshtein | On dp-coloring of graphs and multigraphs[END_REF]. DP-colourings in multigraphs will be described in Chapter 2.

G. G is DP-f -colourable if it is (L, H)-colourable whenever (L, H) is a cover of G and |L(v)| ≥ f (v) for all v ∈ V (G). If G is DP-deg G -colourable
, then G is said to be DP-degree-colourable. Definition 6. The DP-chromatic number, χ DP (G), is the minimum k such that

G is (L, H)-colourable for each choice of (L, H) with |L(v)| ≥ k for all v ∈ V (G).
In DP-colourings, we are mainly concerned with the correspondences between a colour of a vertex and the colours of its adjacent vertices. Hence we can arbitrarily rename the colours while updating the cover as follows. Let (L, H) be a cover for a graph G, and let v be a vertex in

G. If c 1 ∈ L(v) and c 2 / ∈ L(v), then we can define a cover (L ′ , H ′ ) where L ′ (u) =      (L(v) \ {c 1 }) ∪ {c 2 }, if u = v, L(u
vv ′ ∈ E(G), or v = v ′ . The independence number of H is at most |V (G)|, since V (H) is covered by |V (G)| cliques. If H has an independent set I with |I| = |V (G)|, then for each v ∈ V (G)
, there exists a unique c ∈ L(v) such that (v, c) ∈ I. In addition, the same colour c is not chosen for any two adjacent vertices. So we have χ DP (G) ≥ χ ℓ (G).

Fractional colourings

The

Definition 7.

Let G be a graph. We say that c is a fractional colouring of G, of weight a/b.

1. A proper (a : b)-colouring of G is a function c : V (G) → [a] b such that ∀uv ∈ E(G), c(u) ̸ = c(v).
2. The fractional chromatic number of G, denoted χ f (G), is defined by

χ f (G) = inf{ a b
there exists a proper(a : b)-colouring of G}.

Remark 2. A proper k-colouring is the same as a proper (k : 1)-colouring.

Therefore,

∀G, χ f (G) ≤ χ(G).
The fractional chromatic number χ f (G) can equivalently be defined as the fractional relaxation of the integer linear program (1.1) computing the chromatic number. Let G be a graph, we define I (G) to be the set of all independent sets of G, and the fractional chromatic number χ f (G) of G is the solution of the following linear program.

χ f (G) = min I∈I (G) w I such that            w I ∈ [0, 1] for each I ∈ I (G) I∈I (G) v∈I w I ≥ 1 for each v ∈ V (G).
(1.2)

A fractional colouring of weight w of G is any instance within the domain of the above linear program such that w I = w. This equivalent formulation implies that the value of the fractional chromatic number is always attained as the weight of some fractional colouring. Therefore, the infimum in Definition 7 can be replaced with a minimum. Specifically, fractional chromatic numbers are always rational.

Fractional colourings can be defined as probability distributions on the independent sets of a graph G. A graph G has a fractional colouring of weight w if and only if there exists a probability distribution on independent sets of G such that

∀v ∈ V (G), P[v ∈ I] ≥ 1 w
for the independent set I sampled from this distribution.

. Main classical results on proper vertex colourings

There is almost no hope of finding any algorithm of polynomial complexity computing the chromatic number of any graph, since it is strongly believed by the scientific community that P ̸ = NP, while the k-colouring problem is NP-complete.

As the exact computation of the chromatic number of a given graph G appears infeasible in the general case, the initial step would be to bound it in terms of other parameters of G.

Naive bounds for the chromatic number

We first present two lower bounds of χ(G) that are sufficient in many applications to estimate the chromatic number of classical graphs, even though the chromatic number can be arbitrarily larger than both. We know that χ(K n ) = n.

As a result, any graph G that contains K n as a subgraph must require at least n colours in a proper colouring;

∀G, χ(G) ≥ ω(G). A proper k-colouring of G is also a partition of V (G) into k independent sets. Since the size of each independent set is at most α(G), we have k • α(G) ≥ |V (G)|; ∀G, χ(G) ≥ |V (G)| α(G) .
For a given graph G, it is possible to capture both lower bounds ω(G) and

|V (G)| α(G) of χ(G)
ρ(G) := max |V (H)| α(H) | H ⊆ G ≥ max |V (G)| α(G) , ω(G) .
Since being k-colourable is a hereditary property, it holds that

∀G, χ(G) ≥ ρ(G).
For upper bounds, it is easy to bound from above the chromatic number of a graph G in terms of its maximum degree by considering a greedy colouring algorithm. Let G be a graph, and we order the vertices in V (G) arbitrarily. We colour the vertices of G sequentially, assigning the smaller colour which does not appear in the neighbourhood of the considered vertex at each step when there exists one, or adding a new colour to the colouring otherwise. Since

|N G (v)| ≤ ∆(G)
where ∆(G) is the maximum degree of G, we have χ(G) ≤ ∆(G) + 1 for every graph G.

Main classical results for the chromatic number

A well-known objective in graph colouring is to establish adequate conditions that can yield much-improved upper bounds on the chromatic number compared to the straightforward ones. Over the past few decades, considerable research has been conducted in this field, and presented below are some of the key findings in this domain.

Theorem 5 (Four Colour Theorem [START_REF] Robertson | A new proof of the four-colour theorem[END_REF]) For every planar graph G,

χ(G) ≤ 4.
Interestingly, the problem of deciding whether a planar graph is 3-colourable is NP-complete, as proved by Garey, Johnson and Stockmeyer [START_REF] Garey | Some simplified np-complete graph problems. theoritical computer science[END_REF]. Therefore, it seems wise to discuss some sufficient conditions for planar graphs to be 3-colourable. In 1959, Grötzsch's [START_REF] Grotzsch | Ein dreifarbensatz fur dreikreisfreie netze auf der kugel[END_REF] proved the following theorem.

Theorem 6 (Grötzsch's theorem, 1959 [START_REF] Grotzsch | Ein dreifarbensatz fur dreikreisfreie netze auf der kugel[END_REF]) For every planar triangle-free graph G, χ(G) ≤ 3.

In 1976, Steinberg first presented the following conjecture.

Conjecture 1 (Steinberg's conjecture [START_REF] Steinberg | The state of the three color problem[END_REF]) Every planar graph without 4-cycles and 5-cycles is 3-colourable.

This problem has been attracting a substantial amount of attention among graph theorists. It is also one of the six graph theory problems ranked with the 4-star (highest) importance in the Open Problem Garden [START_REF]Problem Garden[END_REF]. As a possible approach towards proving Steinberg's conjecture, Erdős in 1991 (see [START_REF] Steinberg | The state of the three color problem[END_REF])

suggested determining the smallest k such that every planar graph with no cycles of length 4, . . . , k is 3-colourable. The best known upper bound for such a k is 7, which was proved by Borodin, Glebov, Raspaud and Salavatipour [START_REF] Borodin | Planar graphs without cycles of length from 4 to 7 are 3-colorable[END_REF].

Theorem 7 (Borodin, Glebov, Raspaud and Salavatipour, 2005 [19])

Every planar graph with no cycles of length from 4 to 7 is 3-colourable.

In 2017, Cohen-Addad, Hebdige, Král, Li, and Salgado [START_REF] Cohen-Addad | Steinberg's conjecture is false[END_REF] constructed a planar graph to disprove Steinberg's conjecture. It implies that k ≥ 6 for Erdős problem.

Theorem 8 (Cohen-Addad, Hebdige, Král, Li, and Salgado, 2017 [START_REF] Cohen-Addad | Steinberg's conjecture is false[END_REF])

There is a planar graph with no cycles of length 4 or 5 that is not 3-colourable.

There are also some insightful results about the upper bounds of the chromatic number in general graphs.

Theorem 9 (Bipartite graphs characterisation) For every graph G,

χ(G) ≤ 2 ⇐⇒ G contains no odd cycle.
Theorem 10 (Brook's theorem [START_REF] Brooks | On colouring the nodes of a network[END_REF]) For every connected graph G, either G is a complete graph or an odd cycle, or

χ(G) ≤ ∆(G).
Theorem 11 (Johansson-Molloy theorem [START_REF] Johansson | Asymptotic choice number for triangle free graphs[END_REF][START_REF] Molloy | The list chromatic number of graphs with small clique number[END_REF] ) For every triangle-free graph G,

χ(G) ≤ (1 + o(1)) ∆(G) ln ∆(G)
.

All these theorems are sharp, since infinite families of graphs satisfying their constraints and asymptotically reaching the upper bound exist for each of them.

With the exception of the Johansson-Molloy theorem, the sharpness is precise for all of them, as the upper bound and the value achieved by the known infinite families of graphs coincide. However, in the case of the Johansson-Molloy theorem, an asymptotic multiplicative gap of 2 remains between the upper bound and the value attained by Bollobás [START_REF] Bollobás | The independence ratio of regular graphs[END_REF]. He showed that for any integers g and ∆ ≥ 3, there exists a graph with a maximum degree of ∆, girth at least g, and chromatic number at least ∆ 2 ln ∆ . There are still a lot of open problems related to the chromatic number of graphs. Extending Theorem 11 to any H-free graph is one of these issues.

Conjecture 2 (Alon, Krivelevich, Sudakov, 1999 [4]) Let H be some fixed graph. There exists a constant C H > 0 such that, for every H-free graph G,

χ(G) ≤ C H ∆(G) ln ∆(G)
.

To prove Conjecture 2, it is enough to demonstrate its validity when H is a complete graph, since any fixed H is a subgraph of K n(H) , and thus any H-free graph is also K n(H) -free. This conjecture deals with the chromatic number's asymptotic value for graphs with a fixed clique number as ∆ → ∞. The following conjecture, Reed conjecture, is relevant to the case where the maximum degree is arbitrarily near to the clique number.

Conjecture 3 (Reed, 1998 [91]) For every graph G,

χ(G) ≤ ω(G) + ∆(G) + 1 2 .
The following represents one of the most notable partial outcomes in support of Reed's conjecture thus far.

Theorem 12 (Hurley, Verclos, and Kang, 2021 [START_REF] Hurley | An improved procedure for colouring graphs of bounded local density[END_REF]) There is some ∆ 0 such that, for every graph G of maximum degree ∆(G) ≥ ∆ 0 , χ(G) ≤ ⌈0.881(∆(G) + 1) + 0.119ω(G)⌉ .

. Extensions of proper vertex colourings

One can imagine numerous variants of the colouring problem, depending on the application context. Some are augmented variants of the problem, while others are simplified. In this section, we will discuss the most notorious.

Main results on list colourings

Since G has a proper k-colouring if and only if G has an L-colouring with

L(v) = [k], we have χ ℓ (G) ≥ χ(G) for every graph G. Clearly, every k-choosable
graph is k-colourable, but the converse is not true in general. While the chromatic number of a bipartite graph G is at most 2, Erdős, Rubin, and Taylor [START_REF] Rubin | Choosability in graphs[END_REF] showed that the choice number of a bipartite graph G may be arbitrarily large by proving

that χ ℓ (K n,n ) = (1 + o(1)) log 2 n.
On the other hand, some well-known upper bounds on χ(G) in terms of vertex degrees hold for χ ℓ (G) as well. For example, Brook's theorem and the degeneracy upper bound hold for χ ℓ (G). By using a greedy algorithm, we have that:

Theorem 13 If G is k-degenerate, then χ ℓ (G) ≤ k + 1 ≤ ∆(G) + 1.
Alon proved in 2000 [START_REF] Alon | Degrees and choice numbers[END_REF] that the choice number can also be bounded from below as a function of the minimum degree δ(G). Note that it also holds for the average degree.

Theorem 14 (Alon, 2000 [2]) For every graph G,

χ ℓ (G) ≥ ( 1 2 -o(1)) • log 2 (δ(G)).
This result was improved by Saxton and Thomason later.

Theorem 15 (Saxton, Thomason, 2015 [97]) For every graph G,

χ ℓ (G) ≥ (1 + o(1)) • log 2 (δ(G)).
Back in 1998, Alon and Krivelevich [START_REF] Alon | The choice number of random bipartite graphs[END_REF] established that the lower bound stated in Theorem 15 is almost surely asymptotic to the choice number of a random bipartite graph. In the same paper, they proposed the following conjecture.

Conjecture 4 (Alon, Krivelevich, 1998 [START_REF] Alon | The choice number of random bipartite graphs[END_REF]) There exists an absolute constant C > 0 such that for every bipartite graph G,

χ ℓ (G) ≤ C ln ∆(G).
While this conjecture asks a very natural question about a fundamental property of a highly studied graph class, surprisingly, researchers have made very little

progress toward an answer.

In 2019, Molloy [START_REF] Molloy | The list chromatic number of graphs with small clique number[END_REF] further improved the celebrated result of Johansson [START_REF] Johansson | Asymptotic choice number for triangle free graphs[END_REF] which extended Theorem 11 to list colourings.

Theorem 16 (Molloy, 2019 [81]) For every triangle-free graph G,

χ ℓ (G) ≤ (1 + o(1)) ∆(G) ln ∆(G)
.

It implies that the upper bound of the choice number of a bipartite graph is

(1 + o(1)) ∆ ln ∆ .
Recently, Bradshaw improved this upper bound of bipartite graphs in his thesis.

Theorem 17 (Bradshaw, 2022 [20]) If G is a bipartite graph of sufficiently large maximum degree ∆(G), then,

χ ℓ (G) < 0.797 ∆ ln ∆ .
Theorem 17 makes only a modest improvement to the coefficient of the previously known upper bound and is still far away from the conjectured bound of O(ln ∆). Whereas for planar graphs, the issue has been conclusively resolved. In 1994, Thomassen proved a version of the Four Colour Theorem for list colourings.

Theorem 18 (Thomassen, 1994 [101]) For every planar graph G, χ ℓ (G) ≤ 5.

Voigt [START_REF] Voigt | List colourings of planar graphs[END_REF] constructed a planar graph that needs more than four colours to be properly coloured, proving that not all planar graphs are 4-choosable.

Theorem 19 (Voigt, 1993 [106]) There exist planar graphs which are not

4-choosable.

Moreover, Gutner [START_REF] Gutner | The complexity of planar graph choosability[END_REF] established that the problem of determining whether a planar graph is 4-choosable is NP-hard. Thomassen [START_REF] Thomassen | 3-list-coloring planar graphs of girth 5[END_REF] later gave a nice sufficient condition for a planar graph to be 3-choosable.

Theorem 20 (Thomassen, 1995 [102]) For every planar graph G of girth at least 5,

χ ℓ (G) ≤ 3.
The intermediate result between Theorem 18 and Theorem 20 pertains to the choice number of planar graphs without triangles. The conclusion is at most 4, since the degeneracy of triangle-free planar graphs is at most 3.

Main results on DP-colourings

Inspired by Steinberg's conjecture, Borodin [START_REF] Borodin | Colorings of plane graphs: a survey[END_REF] noted that it has remained open since 1996 whether every planar graph without cycles of lengths 4 to 8 is

3-choosable.
Conjecture 5 (Borodin, 2013 [18]) Every planar graph without cycles of lengths 4 to 8 is 3-choosable.

In order to prove such an upper bound for a class of planar graphs, Dvořák

and Postle [START_REF] Dvořák | Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8[END_REF] proposed and heavily used a new tool -DP-colourings. They used vertex identification to deal with a main reduction of their proof. The lists do not matter for DP-colourings (as long as all vertices use the same number of colours). So they can assign every vertex the same list in order to perform vertex identification which is usually not possible in a list colouring settings.

Theorem 21 (Dvořák, Postle, 2018 [38]) Every planar graph G without cycles of lengths 4 to 8 is 3-choosable.

As mentioned above, we have χ DP (G) ≥ χ ℓ (G) for every graph G. Some upper bounds on the choice number hold for the DP-chromatic number as well. For example, Dvořák and Postle observed that χ DP (G) ≤ k + 1 for every k-degenerate graph G. Indeed, we may choose a colour for each vertex v greedily from L(v)

avoiding the colours adjacent in its cover H to the colours already chosen for neighbours of v. Dvořák and Postle [START_REF] Dvořák | Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8[END_REF] noted that Theorem 18 and Theorem 20 immediately extend to DP-colourings.

Theorem 22 (Dvořák, Postle, 2018 [38]) For every planar graph G, χ DP (G) ≤ 5.

Theorem 23 (Dvořák, Postle, 2018 [38]) For every planar graph G of girth at least 5,

χ DP (G) ≤ 3.
In 2019, Bernshteyn verified Theorem 16 in the context of DP-colourings.

Theorem 24 (Bernshteyn, 2019 [10]) For every triangle-free graph G,

χ DP (G) ≤ (1 + o(1)) ∆(G) ln ∆(G)
.

On the other hand, DP-colourings and list colourings are strikingly different.

Recall that due to a celebrated result of Alon [START_REF] Alon | Degrees and choice numbers[END_REF], the choice number of the graphs with average degree d is Ω(log d), and this bound is sharp for "small" bipartite graphs. However, Bernshteyn proved that the DP-chromatic number of such graphs is close to linear in d.

Theorem 25 (Bernshteyn, 2016 [9]) For every graph with average degree

d, χ DP (G) = Ω( d ln d
).

Important tools in the study of list colourings that do not generalise to the framework of DP-colourings are the orientation theorems of Alon and Tarsi [START_REF] Alon | Colorings and orientations of graphs[END_REF] and the closely related Bondy-Boppana-Siegel lemma (see [START_REF] Alon | Colorings and orientations of graphs[END_REF]). Indeed, they can be used to prove that even cycles are 2-choosable, while the DP-chromatic number of any cycle is 3, regardless of its length.

Theorem 26 (Alon, Tarsi, 1992 [5]) Every planar bipartite graph is

3-choosable.

However, Bernshteyn and Kostochka [START_REF] Bernshteyn | On differences between DP-coloring and list coloring[END_REF] showed that Theorem 26 does not hold for DP-colourings.

Theorem 27 (Bernshteyn, Kostochka, 2019 [11]) There exists a bipartite planar graph G with χ DP (G) = 4.

Main results on fractional colourings

Firstly, let us analyse some observations about the bounds of the fractional chromatic number. As we mentioned previously, a k-colouring of graph G can be viewed as a specific type of fractional colouring of weight k of G, where the weight

w I is one if I is a monochromatic class in the k-colouring, w I is 0 otherwise. So we have χ f (G) ≤ χ(G). Furthermore, if W is a clique of G,
χ f (G) ≥ ω(G). More generally, χ f (G) ≥ χ f (H) for any subgraph H of G.
Another lower bound on the fractional chromatic number of a graph G is related to its independence number α(G). Indeed, the total weight induced by an independent set I of G on its vertex set is at most ω I α(G), so we have

|V (G)| ≤ v∈V (G) w(v) ≤ I∈F (G) α(G)w I = α(G) • I∈F (G) w I .
It means that the weight of any fractional colouring of G must be at least

|V (G)| α(G) . Recall that the Hall ratio ρ(G) of G as ρ(G) := max{ |V (H)| α(H) | H ⊆ G}.
By combining the two previously mentioned lower bounds, we have the following observations:

max |V (G)| α(G) , ω(G) ≤ ρ(G) ≤ χ f (G) ≤ χ(G) ≤ ∆(G) + 1.
We may wonder how close the fractional chromatic number can deviate from the Hall ratio. In 2020, Dvořák, Ossona de Mendez, and Wu [START_REF] Dvořák | 1-subdivisions, the fractional chromatic number and the hall ratio[END_REF] conclude that the fractional chromatic number can not be bounded by any function of the Hall ratio.

If G is a perfect graph, then the clique number ω(G) equals to the chromatic number χ(G), and therefore also equal to the fractional chromatic number χ f (G).

A perfect graph G is a graph with the property that, for every induced subgraph

H of G, ω(H) = χ(H).
Perfect graphs are a class of graphs that do not contain any odd holes or odd antiholes, as conjectured by Berge [START_REF] Berge | Farbung von graphen, deren samtliche bzw. deren ungerade kreise starr sind[END_REF] in 1961 and proven by Chudnovsky, Robertson, Seymour, and Thomas, [START_REF] Chudnovsky | The strong perfect graph theorem[END_REF] in 2006. On the other hand, Brooks [START_REF] Brooks | On colouring the nodes of a network[END_REF] established in 1941 that equality holds between χ(G) and ∆(G) + 1 only for cliques and odd cycles. Since the fractional chromatic number of an odd cycle C 2k+1 is 2k+1 k , the only graphs G for which χ f (G) = ∆(G) + 1 are cliques. Moreover, equality holds between the Hall ratio of G and its fractional chromatic number for example when G is vertex transitive.

Results on fractional colourings

Given a graph H, we let χ f (d, H) be the supremum of the fractional chromatic numbers over all H-free graphs of maximum degree at most d. As we already mentioned in Theorem 11, it implies that

χ f (d, K 3 ) = (1+o(1)) d/ ln d as d → ∞,
and one can infer from a study of random d-regular graphs by Bollobás [START_REF] Bollobás | The independence ratio of regular graphs[END_REF] that

χ f (d, K 3 ) ≥ d 2 ln d .
However, there is still a significant range of degrees that are not covered by the bound for triangle-free graphs, i.e. when ∆ < ∆ ϵ , which is larger than 20 2/ϵ . The determination of the maximum value of χ f (G) among triangle-free graphs with a maximum degree of 3 has been a long-standing open problem.

We define ρ(d, g) to be the supremum of the Hall ratios over all graphs of maximum degree at most d and girth at least g. We also let ρ(d, ∞) be the limit as In 1979, Staton [START_REF] Staton | Some ramsey-type numbers and the independence ratio[END_REF] established that ρ(d, 4) ≤ 5d-1 5 , in particular implying that ρ(3, 4) ≤ 14 5 . The two graphs depicted in Figure 1.4, called the graphs of Fajtlowicz and of Locke, have 14 vertices each, girth 5, and no independent set of order 6. It follows that ρ(3, 4) = 14 5 = ρ [START_REF] Alon | The choice number of random bipartite graphs[END_REF][START_REF] Alon | Colorings and orientations of graphs[END_REF]. It is known that the graphs of Fajtlowicz and of Locke are the only two cubic triangle-free and connected graphs with Hall ratio 14 5 . It follows from a result of Fraughnaugh and Locke [START_REF] Fraughnaugh | 11/30 (finding large independent sets in connected triangle-free 3-regular graphs)[END_REF] for graphs with more than 14 vertices completed by an exhaustive computer check on graphs with at most 14 vertices performed by Bajnok and Brinkmann [START_REF] Bajnok | On the independence number of triangle free graphs with maximum degree three[END_REF].

The determination of χ f (3, K 3 ) was finally settled in [START_REF] Dvořák | Subcubic triangle-free graphs have fractional chromatic number at most 14/5[END_REF] by Dvořák, Sereni, and Volec.

Theorem 28 (Dvořák, Sereni, and Volec, 2014 [39]) χ f (3, K 3 ) = 14 5 .

In 1983, Jones [START_REF] Jones | Independence in graphs with maximum degree four[END_REF] established that ρ(4, 4) = 13 4 . Only one connected graph is 29 Theorem 29 (Molloy, Reed, 2002 [82]) For every graph G,

χ f (G) ≤ ω(G) + ∆(G) + 1 2 .
It implies that χ f (4, K 3 ) lies between 3.25 and 3.5. In Chapter 3, I will prove the following.

Theorem 30 (Dai, Ouyang, Pirot, and Sereni, 2023 [START_REF] Dai | Beyond the fractional reed bound for triangle-free graphs[END_REF]) χ f (4, K 3 ) < 3.4663.

. Hamilton-connectivity

In 1857, the Irish mathematician Sir William Hamilton (1805-1865) invented a game (Icosian Game, now also known as Hamilton's puzzle) of travelling around the edges of a graph from vertex to vertex. In a letter to his friend Graves, Hamilton described the game as a dodecahedron-based mathematical game. Every vertex of the dodecahedron is labelled with the name of a city, and the goal of the game is to find a cycle along the edges of the dodecahedron such that every vertex is visited exactly once, and the ending point is the same as the starting point; one is therefore looking for a Hamiltonian cycle of the dodecahedron (see Figure 1.6).

Since then hamiltonicity, which aims at determining whether or not a graph G contains a Hamiltonian cycle, has been at the origin of a whole branch of graph theory.

Hamiltonicity has many applications in different fields, including network design and fault tolerance, DNA sequencing, robotics and automated path planning, circuit design, etc. Here we give a Traveling Salesman Problem as an example.

Consider a graph with a set of cities and the distances between them. The task is to find a route that visits each city exactly once and returns to the starting city, minimising the total distance travelled. The goal of the graph is to find a Hamiltonian cycle such that its distance is minimum. However, the Hamiltonian problem is NP-complete [START_REF] Garey | The planar hamiltonian circuit problem is np-complete[END_REF]. Finding a Hamiltonian cycle or path in a general graph is computationally tricky and may require significant computational resources.

σ k (G) = min S⊆V (G) v∈S deg G (v) |S| = k, S is an independent set in G , σ k (G) = min S⊆V (G) v∈S deg G (v) -| v∈S N G (v)| |S| = k, S is an independent set in G .
The earliest known result based on a degree condition was given by Dirac [START_REF] Dirac | Some theorems on abstract graphs[END_REF] in 1952.

Theorem 31 (Dirac, 1952 [35]) Let G be a graph on

n vertices. If δ(G) ≥ n 2 , then G is Hamiltonian.
The lower bound of Dirac's theorem is known to be sharp. To illustrate this, let's consider a complete bipartite graph K n,n+1 with 2n + 1 distinct vertices.

Clearly, the minimum degree of K n,n+1 is n, and it is not Hamiltonian. Unless a few more conditions are added, Dirac's theorem cannot be relaxed without cancelling the conclusion.

Over time, numerous scientists extended Dirac's condition to encompass broader scenarios. In 1960, Ore [START_REF] Ore | A note on hamiltonian circuits[END_REF] gave the following generalised theorem.

Theorem 32 (Ore, 1960 [83]) Let G be a graph on n vertices. If σ 2 (G) ≥ n, then G is Hamiltonian.

As well as Dirac's theorem, Ore's theorem also has a strict requirement on the bound of n in order to maintain its conclusion. An example for the sharp of Ore's theorem is the complete bipartite graph K n-1 Theorem 33 (Flandrin, Jung, Li, 1991 [44]) If G is a 2-connected graph with n vertices such that σ 3 (G) ≥ n, then G is Hamiltonian.

In the same paper [START_REF] Flandrin | Hamiltonism, degree sum and neighborhood intersections[END_REF], they also give a condition on σ 3 (G) to show the existence of a Hamiltonian path.

Theorem 34 (Flandrin, Jung, Li, 1991 [44]) If G is a connected graph with n vertices such that σ 3 (G) ≥ n -1, then G has a Hamiltonian path.

The constant stream of results in hamiltonicity continues to supply us with new and interesting theorems and still further questions. One of them is about Hamilton-connectivity. In fact, determining whether a graph is Hamilton-connected is NP-complete [START_REF] Garey | Computers and Intractability:A Guide to the Theory of NP-Completeness[END_REF]. Researchers try to find sufficient degree and neighbourhood union conditions for Hamilton-connected graphs. It was first introduced by Ore in 1963.

Theorem 35 (Ore, 1963 [84])

If G is a graph with σ 2 (G) ≥ n + 1 where n is the order of G, then G is Hamilton-connected.
In 1989, Flandrin, Gould, Jacobson, Schelp gave a sufficient degree sums condition of 3-connected graphs.

Theorem 36 (Flandrin, Gould, Jacobson, Schelp, 1989 [43])

If G is 3-connected with n vertices such that σ 2 (G) ≥ 2n+1 3 , then G is Hamilton connected.
This result was generalised by Wei in 1993.

Theorem 37 (Wei, 1993 [107]) If G is a 3-connected graph with n vertices such that σ 3 (G) ≥ n + 1, then G is Hamilton-connected.

There are plenty of results about hamiltonicity and Hamilton-connectivity, here we have only provided partial elegant results. For more results, we would mention the excellent survey by Gould [START_REF] Gould | Updating the hamiltonian problem-a survey[END_REF][START_REF] Gould | Advances on the hamiltonian problem-a survey[END_REF].

. Extensions of Hamilton-connectivity

Hamilton-connectivity plays an important role in computer networks. The parallel computer's processors are connected through a network. Its architecture can be visualized as a graph, with the communication lines serving as the edges and the vertices as the processors. To ensure the resilience of the communication in the case that a node fails along one link, we must maintain communication links within several pairs of processors. The objective in a graph is to find internally-disjoint paths between these pairs where each path should be unique and share no common nodes with any other path. However, there are numerous needs that compete with one another when building the architecture of computer networks. It is almost impossible to design a network that is optimal from all aspects. One has to design a suitable network depending on the requirements and their properties.

It inspired researchers to extend Hamilton-connectivity by the context needed for its application.

Spanning connectivity

In some specific application contexts [START_REF] Lin | On the spanning w-wide diameter of the star graph[END_REF][START_REF] Lin | The super connectivity of the pancake graphs and the super laceability of the star graphs[END_REF], Hsu in 1984 introduced the concept of a container and indicated that the container plays an essential role in evaluating the reliability and performance of interconnectivity networks [START_REF] Hsu | On container width and length in graphs, groups, and networks-dedicated to professor paul erdös on the occasion of his 80th birthday[END_REF].

Definition 8. Let G be a graph.

1. A k-container of G between u and v, C k (u, v), is a set of k-internally-disjoint paths between u and v.
2. A spanning k-container, (abbreviated as k * -container), is a k-container that contains all vertices vertices of V (G).

A graph

(G), is the maximum integer k such that G is w * -connected for 1 ≤ w ≤ k if G is 1-container-connected. 5. A graph G is super spanning connected if κ * (G) = κ(G).
Obviously, the complete graph

K n is super spanning connected if n ≥ 2.
Spanning connectivity is a hybrid concept of hamiltonicity and connectivity. We can obtain the following properties about the container. Theorem 38 (Lin, Huang, Hsu, 2007 [75])

If G is a graph with δ(G) ≥ n(G)+k-2 2
, then G is k * -connected.

In 2008, Hsu and Lin [START_REF] Hsu | Graph theory and interconnection networks[END_REF] gave a Ore-type sufficient condition of k * -connected graphs.

Theorem 39 (Lin, Huang, Tan, Hsu, 2008 [START_REF] Lin | On spanning connected graphs[END_REF]) Let k be a positive integer.

If σ 2 (G) ≥ n(G) + k -2, then G is k * -connected.
More results about the spanning connectivity of graphs have been studied

extensively [START_REF] Hsu | The spanning connectivity of the (n, k)-star graphs[END_REF][START_REF] Hsu | Graph theory and interconnection networks[END_REF][START_REF] Lin | On the spanning w-wide diameter of the star graph[END_REF][START_REF] Lin | The super connectivity of the pancake graphs and the super laceability of the star graphs[END_REF][START_REF] Lin | On the spanning connectivity of graphs[END_REF][START_REF] Hsu | Graph theory and interconnection networks[END_REF][START_REF] Sabir | Generalizations of the classics to spanning connectedness[END_REF][START_REF] Tsai | The super-connected property of recursive circulant graphs[END_REF].

k-fan connected graphs

In 2009, Lin, Tan, Hsu, and Hsu [START_REF] Lin | On the spanning fan-connectivity of graphs[END_REF] gave a definition of k-fan connected graphs, which is a Menger-type concept similar to the spanning connectivity of a graph.

Definition 9. For any integer k ≥ 2, let v be a vertex of a graph G and U = {u 1 , u 2 , . . . , u k } be a subset of V (G) \ {v}.

1. A (v, U )-fan is a set of internally-disjoint paths P 1 , P 2 , . . . , P k such that

P i is a path connecting v and u i for 1 ≤ i ≤ k. 2. If a (v, U )-fan spans G, then it is called a spanning (v, U )-fan of G.
3. If G has a spanning (v, U )-fan for every vertex v of G and every subset

U of V (G) \ {v} with |U | = k, then we call G is k-fan-connected or k * f -connected. 4. The spanning fan-connectivity of a graph G, κ * f (G), is defined as the largest integer k such that G is w * f -connected for 1 ≤ w ≤ k if G is a 1 * f -connected graph. Remark 4.
1. It is proved by Dirac [36] that a graph G is k-connected if and only if it has at least k + 1 vertices and there exists a (v, U )-fan for every choice of v and U with |U | ≤ k and v / ∈ U .

2. Every 1 * -connected graph is 1 * f -connected. Moreover, every

1 * f -connected graph that is not K 2 is 2 * f -connected.
Lin, Tan, Hsu and Hsu [START_REF] Lin | On the spanning fan-connectivity of graphs[END_REF] discussed the relationship among κ * f (G), κ * (G), and κ(G).

Theorem 40 (Lin, Tan, Hsu, Hsu, 2009 [76])

For any 1 * f -connected graph, κ * f (G) ≤ κ * (G) ≤ κ(G). Moreover, κ * f (G) ≤ κ * (G) ≤ κ(G) = n(G) -1 if and only if G is a complete graph.
Furthermore, they presented an Ore-type sufficient condition for a graph to be κ * f -connected.

Theorem 41 (Lin, Tan, Hsu, Hsu, 2009 [76]) Let G be a graph and k ≥ 2 be an integer.

If σ 2 (G) ≥ n(G) + k -1, then G is κ * Theorem 42 (Li, Maezawa, Tian [70]) Let G be an n-vertex graph. If G is (k + 1)-connected and σ 3 (G) ≥ n + k -1 with k ≥ 2, then G is k-fan-connected.

k-linked connected graphs

We introduce a significant definition, k-linked graphs, which is also related to the connectivity of graphs. Linkage structure plays an important role in the study of graph minors.

Definition 10. For an integer k ≥ 2, a graph is k-linked if it has at least 2k vertices and for every sequence s 1 , s 2 , . . . , s k , t 1 , t 2 , . . . , t k of distinct vertices there exist disjoint paths P 1 , . . . , P k such that the ends of P i are s i and t i for i = 1, 2, . . . , k.

Clearly, every k-linked graph is k-connected. The converse is not true, however, which brings up the natural question of how much connectivity, as a function f (k), is necessary to ensure that a graph is k-linked. After a series of papers by Jung [START_REF] Jung | Eine verallgemeinerung des n-fachen zusammenhangs für graphen[END_REF], Larman and Mani [START_REF] Larman | On the existence of certain configurations within graphs and the 1-skeletons of polytopes[END_REF], Mader [START_REF] Mader | Homomorphieeigenschaften und mittlere kantendichte von graphen[END_REF], and Robertson and Seymour [START_REF] Robertson | Graph minors. xiii. the disjoint paths problem[END_REF], the first linear upper bound for f , namely f (k) ≤ 22k, was proved by Bollobás and Thomason [START_REF] Bollobás | Highly linked graphs[END_REF].

In 2006, Kawarabayashi, Kostochka, and Yu [START_REF] Kawarabayashi | On sufficient degree conditions for a graph to be-linked[END_REF] improved the bound of

f (k) to 12k.
Theorem 43 ([64]) Every 2k-connected graph G with e(G) ≥ 6kn(G) is k-linked. In particular, every 12k-connected graph is k-linked.

They also determined sharp minimum degree and degree sum conditions for a graph G of order at least 2k to be k-linked.

Theorem 44 ([64]) Let G be a graph on n ≥ 2k vertices.

δ(G) ≥              n+2k-3 2 , if n ≥ 4k -1, n+5k-5 3 , if 3k ≤ n ≤ 4k -2, n -1, if 2k ≤ n ≤ 3k -1. or σ 2 (G) ≥              n + 2k -3, if n ≥ 4k -1, 2(n+5k) 3 -3, if 3k ≤ n ≤ 4k -2, 2n -3, if 2k ≤ n ≤ 3k -1.
then G is k-linked. These bounds are the best possible.

Thomas and Wollan [START_REF] Thomas | An improved linear edge bound for graph linkages[END_REF] used the bound δ(G) ≥ n+2k-3

2
to give sufficient conditions for a graph to be k-linked in terms of connectivity.

Theorem 45 Theorem 46 (Dai, Li, Ouyang, Tian, [START_REF] Dai | On (2,k)-hamilton-connected graphs[END_REF])

([100]) If G is 10k-connected, then G is k-linked. (k 1 , k 2 )-
Let G be an n-vertex graph. If G is (5k -2)-connected and σ 2 (G) ≥ n + k -2 with k ≥ 2, then G is (2, k)-Hamilton-connected. Moreover, the bound of σ 2 (G) is sharp.
Another result obtained is about (k 1 , k 2 )-Hamilton-connectivity which is also a tight sufficient condition.

Theorem 47 (Dai, Li, Ouyang, Tian, [START_REF] Dai | On (2,k)-hamilton-connected graphs[END_REF]) Let G be an n-vertex

graph. If σ 2 (G) ≥ n + k 1 k 2 -2 with k 1 , k 2 ≥ 2, then G is (k 1 , k 2 )-Hamilton-connected. Moreover, the bound of σ 2 (G) is sharp.
The two theorems above will be stated Theorem 59 and Theorem 58 in Chapter 4.

. Contribution and outline of the thesis

In this section, we summarise the main works and the organization of this thesis.

(1) We extend the bound of list colourings on 2-connected bipartite outerplanar graphs to DP-colourings. In 2008, Hutchinson [START_REF] Hutchinson | On list-coloring outerplanar graphs[END_REF] showed that • if a 2-connected bipartite outerplanar graph G has a list of colors

L(v) for each vertex v with |L(v)| ≥ min{deg G (v), 4}, then G is L-colorable; and
• if a maximal outerplanar graph G with at least four vertices has a

list of colors L(v) for each vertex v with |L(v)| ≥ min{deg G (v), 5}, then G is L-colorable.
She also showed the lower bounds are sharp in the sense that the lower bound 4 for 2-connected bipartite outerplanar graphs (resp. 5

for maximal outerplanar graph) cannot be replaced by 3 (resp. 4).

Our [START_REF] Molloy | Graph colouring and the probabilistic method[END_REF]. It is believed that this bound is not tight for any d ≥ 3. For d ≥ 17, Pirot and Sereni [START_REF] Pirot | Fractional chromatic number, maximum degree, and girth[END_REF] have used hard-core distributions on the independent sets of triangle-free graphs in order to derive the best-known upper bounds for χ f (d, K 3 ). For the case d = 4, Jones [START_REF] Jones | Independence in graphs with maximum degree four[END_REF] proved that for every triangle-free graph G of maximum degree 4 on n vertices, the size of maximum independent sets is at least 4n 13 . This implies that χ f (4, K 3 ) ≤ 13 4 if we restrict its definition to the class of vertex-transitive graphs. In general, χ f (4, K 3 ) lies between 3.25 and 3.5

(by the fractional Reed bound). We use the methodology introduced by Pirot and Sereni [START_REF] Pirot | Fractional chromatic number, maximum degree, and girth[END_REF] together with mixed probability distributions in order to prove that χ f (4, K 3 ) < 3.4663. This work is shown in Chapter 3.

[Corresponding paper: Beyond the fractional Reed bound for triangle-free graphs, in preprint, with Qiancheng Ouyang, François Pirot, and Jean-Sébastien Sereni.]

(3) Inspired by the definition of spanning connectivity and k-fan connected graphs, we study (k 1 , k 2 )-Hamilton-connected graphs. We prove that an

n-vertex graph G is (2, k)-Hamilton-connected if G is (5k -4)-connected with σ 2 (G) ≥ n + k -2 where k ≥ 2. We also prove that if σ 2 (G) ≥ n + k 1 k 2 -2 with k 1 , k 2 ≥ 2, then G is (k 1 , k 2 )-Hamilton-connected.
Moreover, we construct two graphs to show that our results are sharp. This work is discussed in Chapter 4.

-On DP-colourings of outerplanar graphs

In Chapter 1, we have introduced the definition of DP-colourings on simple graphs and related results. This chapter focuses mainly on our work with DP-colourings.

. Introduction

For list colourings, we have known that researchers try to make some upper bounds on χ(G) in terms of vertex degrees hold for χ ℓ (G) as well. For example, Brook's theorem and the degeneracy upper bound hold for χ ℓ (G). Furthermore, Borodin [START_REF] Borodin | Problems of colouring and of covering the vertex set of a graph by induced subgraphs[END_REF][START_REF] Borodin | Criterion of chromaticity of a degree prescription[END_REF] and independently Erdős, Rubin, and Taylor [START_REF] Erdős | Choosability in graphs[END_REF] generalised Brook's theorem to degree-list assignments. Recall that a list assignment L is

called a degree-list assignment if |L(v)| ≥ deg G (v) for every v ∈ V (G). A graph G is said to be degree-choosable if G admits an L-colouring for every degree-list assignment L. A block of G, or 2-connected component, is a maximal (therefore induced) 2-connected subgraph of G.
Theorem 48 ([16, 17, 40], a simple proof in [START_REF] Kostochka | The colour theorems of brooks and gallai extended[END_REF]) A connected graph G is not degree-choosable if and only if G is a Gallai tree, that is, each block of G is isomorphic to K n for some integer n or C n for some odd integer n.

Hutchinson [START_REF] Hutchinson | On list-coloring outerplanar graphs[END_REF] studied the extension problem of a degree-list colouring problem on outerplanar graphs. By induction, an outerplanar graph is easily seen to be 3-choosable since it contains vertices of degree 2. The question she asked involves a mixture of these two hypotheses: if a 2-connected outerplanar graph satisfies|L(v)| ≥ min{deg(v), 4} for every vertex v, is it L-list colourable provided it does not form a Gallai tree of maximum degree at most 4? She showed that the answer is yes when the graph is bipartite, but the answer is no in general due to an example of Kostochka [67]; Hutchinson [START_REF] Hutchinson | On list-coloring outerplanar graphs[END_REF] showed the lower bounds are sharp in the sense that the lower bound 4 in Theorem 49 (resp. 5 in Theorem 50) cannot be replaced by 3 (resp. 4). Note that all conditions of Hutchison's results are needed.

Theorem 49 ([59]) Let G be a 2-connected, outerplanar bipartite graph. For any list assignments L with |L(v)| ≥ min{deg G (v), 4} for every vertex v ∈ V (G), G has an L-colouring.

Theorem 50 ([59]) Let G be a 2-connected edge-maximal outerplanar graph with at least three vertices that is not K 3 with identical 2-lists at each vertex. For any list assignments

L with |L(v)| ≥ min{deg G (v), 5} for every vertex v ∈ V (G), G has an L-colouring.
We mainly study whether Theorems 49 and 50 hold in the setting of DP-colourings. To better illustrate our results, we first propose a definition of DP-colourings that applies to multigraphs and graphs.

Definition 12.

Let G be a multigraph (possibly having multiple edges but no loops) and L be a list assignment of G.

(i) The vertex set of H is u∈V (G) ({u} × L(u)) = {(u, c) : u ∈ V (G), c ∈ L(u)}.
(ii) For every u ∈ V (G), the set {u} × L(u) induces a clique in H. (

) When |L(u)| = [k] for each u ∈ V (G) (that is, when we consider a proper k-colouring), then the M L -cover of G is isomorphic to the graph G2K k , 2
which is the Cartesian product of G and the complete graph K k . The Cartesian product of graphs G and H is the graph G2H whose vertex

set is V (G) × V (H) and edge set is the set of all pairs (u 1 , v 1 )(u 2 , v 2 ) such that either u 1 u 2 ∈ E(G) and v 1 = v 2 , or v 1 v 2 ∈ E(H) and u 1 = u 2 .
We want to generalise Theorems 49 and 50 to hold in the DP-colouring setting.

The following problem corresponds to Theorem 49.

Problem 1 Let G be a 2-connected, outerplanar bipartite graph and L be a list assignment with |L(v)| ≥ min{deg G (v), 4} for every vertex v ∈ V (G). Does G admit an M L -colouring for any matching assignment over L unless G is an even cycle?

The answer to this problem is no, as we show by finding counterexamples.

Note that even cycles satisfying the condition of Problem 1 do not admit an M L -colouring for some matching assignments over L by Theorem 52 (ii) for t = 1.

Theorem 51 There exist infinitely many counterexamples to Problem 1.

For the setting on DP-colourings of Theorem 49, our result is stronger than it.

In fact, we solve all the 2-connected outerplanar graphs, not only bipartite graphs.

Before giving the statement of our result, we need to introduce some special graphs and a related result. For two graphs G and H and a vertex u of G, blowing up u to H is the operation of replacing u by H and joining each vertex of H to every neighbour in G of u. Let n and t be positive integers. • The t-fat ladder of length n is obtained from the ladder of length n by blowing up every vertex to a complete graph K t .

• The ladder of length n is C n 2K 2 . The left graph in
• The t-fat Möbius ladder of length n is obtained from the Möbius ladder of length n by blowing up every vertex to a complete graph K t .

For a graph G and an integer t, we denote by G t the multigraph obtained from G by replacing every edge of G with t multiple edges. A multigraph G is called a complete multigraph, if the graph obtained from G by replacing every set of multiple edges with a single edge is a complete graph. Kim and Ozeki obtained the following result (in fact they showed a result stronger than Theorem 52).

Theorem 52 ([65]) Let G be a 2-connected multigraph not isomorphic to a complete multigraph with order at least four and let L be a list assignment of G with |L(v)| ≥ deg G (v) for each v ∈ V (G). Then G does not admit an M L -colouring if and only if G is isomorphic to C t n for some integers n and t such that the following hold.

(i) If n is an odd integer, then M L -cover is isomorphic to t-fat ladder of length n.

(ii) If n is an even integer, then M L -cover is isomorphic to t-fat Möbius ladder of length n.

Given a graph G and a list assignment L of G, if an M L -cover of G satisfies one of the two conditions in Theorem 52, then we say (G, L, M L ) is bad. We prove the following main result in this chapter, which is a generalisation of Theorem 50.

Theorem 53 Let G be a 2-connected outerplanar graph. Let L be a list assignment of

G with |L(v)| ≥ min{deg G (v), 5} for every v ∈ V (G).
Then G admits an M L -colouring for each matching assignment M L over L unless (G, L, M L ) is bad.

The possible bad triples (G, L, M L ) in Theorem 53 are as follows: either (i) G is isomorphic to C n for an odd integer n and its M L -cover is isomorphic to the ladder of length n; or (ii) G is isomorphic to C n for an even integer n and M L -cover is isomorphic to the Möbius ladder of length n.

Let G be a graph, L be a list assignment of G, and M L be a matching assignment over L. To simplify notation, we can regard the vertex set of the

M L -cover of G as ∪ u∈V (G) L(u) instead of ∪ u∈V (G) {u} × L(u). Similarly, L ′ (u) denote {u} × L ′ (u) for L ′ (u) ⊆ L(u).

. The proof of Theorem 51

In this section, we prove Theorem 51: There exist infinitely many counterexamples to Problem 1.

u 0 v 0 w 0 x 3 y 3 x 6 y 6 Figure 2.2:
The graph H 0 .

We begin this section with an easy but useful fact about independent sets in Möbius ladders. It is clear to obtain the following fact by the definition of the Möbius ladder of length k.

Fact 3 Let M be a Möbius ladder of length k. Then the size of any independent set of M is at most k -1 when k is even.

We are now ready to prove Theorem 51 by constructing a graph G in this section. Let L be a list assignment with |L(v)| ≥ min{deg G (v), 4} for every vertex v ∈ V (G). Our goal is to prove that G does not admit an M L -colouring for a given matching assignment over L.

In fact, G consists of a series of subgraphs. Firstly, we construct a base subgraph H 0 (see Figure 2.2) of G. Let H 0 be a connected outerplanar graph satisfying the following conditions:

(i) The vertex set of H 0 is {u 0 , v 0 , w 0 , x 1 , x 2 , . . . , x 8 , y 1 , y 2 , . . . , y 8 }.

(ii) There exists the walk v 0 x 8 x 7 . . . x 1 u 0 y 1 y 2 . . . y 8 w 0 u 0 v 0 and it is an outer walk of H 0 .

(iii) The edge set of H 0 is the edges of the outer walk of (ii) and {u 0 x 3 , x 3 x 6 , v 0 x 6 , u 0 y 3 , y 3 y 6 , w 0 y 6 }.

Note that H 0 is symmetric with respect to u 0 . Let L be a list assignment with

|L(v)| ≥ min{deg H 0 (v), 4} for every vertex v ∈ V (H 0 ). For 1 ≤ i ≤ 4, let u i 0 , v i
0 , and w i 0 be elements of L(u 0 ), L(v 0 ), and L(w 0 ), respectively. Similarly, for 1 ≤ i ≤ 4, let x i 3 , x i 6 , y i 3 , and y i 6 be elements of L(x 3 ), L(x 6 ), L(y 3 ), and L(y 6 ), respectively. We construct an M L -cover J 0 of H 0 such that

(i) Each of J 0 [{u 1 0 , u 2 0 , x 1 3 , x 2 3 } ∪ L(x 1 ) ∪ L(x 2 )], J 0 [{x 3 3 , x 4 3 , x 3 6 , x 4 6 } ∪ L(x 4 ) ∪ L(x 5 )], and J 0 [{v 1 0 , v 2 0 , x 1 6 , x 2 6 } ∪ L(x 7 ) ∪ L(x 8 )
] induces a Möbius ladder of length four.

(ii) Each of J 0 [{u 3 0 , u 4 0 , y 1 3 , y 2 3 }∪ L(y 1 )∪ L(y 2 )], J 0 [{y 3 3 , y 4 3 , y 3 6 , y 4 6 }∪ L(y 4 )∪ L(y 5 )], and J 0 [{w 1 0 , w 2 0 , y 1 6 , y 2 6 } ∪ L(y 7 ) ∪ L(y 8 )] induces a Möbius ladder of length four.

(iii) u 1 0 v 4 0 , u 2 0 v 3 0 , u 3 0 w 4 0 , u 4 0 w 3 0 ∈ E(J 0 ).
Note that J 0 is symmetric with respect to L(u 0 ).

Claim 2.2.1 Let I 0 be an independent set of J 0 with

|I 0 | = |H 0 |. If u i 0 is in I 0 for some i ∈ {1, 2}, then v i+2 0 is in I 0 . If u i 0 is in I 0 for some i ∈ {3, 4}, then w i 0 is in I 0 .
Proof. By symmetry, we may assume that u 1 0

∈ I 0 . Since J 0 [{u 1 0 , u 2 0 , x 1 3 , x 2 3 } ∪ L(x 1 ) ∪ L(x 2 )
] is a Möbius ladder of length four, it follows from Lemma 3 that x 1 3 , x 2 3 / ∈ I 0 and so either x 3 3 or x 4 3 is in

I 0 . Since J 0 [{x 3 3 , x 4 3 , x 3 6 , x 4 6 } ∪ L(x 4 ) ∪ L(x 5 )
] is a Möbius ladder of length four, it follows from Lemma 3 that x 3 6 , x 4 6 / ∈ I 0 and so either x 1 6 or x 2 6 is in

I 0 . Since J 0 [{v 1 0 , v 2 0 , x 1 6 , x 2 6 } ∪ L(x 7 ) ∪ L(x 8 )
] is a Möbius ladder of length four, it follows from Lemma 3 that v 1 0 , v 2 0 / ∈ I 0 and so either

v 3 0 or v 4 0 is in I 0 . Since u 1 0 ∈ I 0 and u 1 0 v 4 0 ∈ E(G), v 3 0 is in I 0 .
For i ≥ 1, let H i be a graph isomorphic to H 0 and let u i , v i , and w i be vertices of H i corresponding to u 0 , v 0 , and w 0 , respectively. For i ≥ 1 and 1 ≤ j ≤ 4, let J i be an M L -cover of H i isomorphic to J 0 and let u j i , v j i , and w j i be vertices of J i corresponding to u j 0 , v j 0 , and w j 0 , respectively. Let G 9 be the graph obtained from H 0 , . . . , H 9 by adding the edges v i w i+1 and u i u i+1 for each 0 ≤ i ≤ 8 and u 0 u 3 , u 3 u 6 , u 6 u 9 , u 9 u 0 . We construct an M L -cover J of G 9 such that

(i) v 3 i w 4 i+1 , v 4 i w 3 i+1 ∈ E(J) for each 0 ≤ i ≤ 8, (ii) u 1 i u 3 i+1 , u 2 i u 4 i+1 ∈ E(J) for each 0 ≤ i ≤ 8, (iii) J[{u 1 0 , u 2 0 , u 1 3 , u 2 3 , u 1 6 , u 2 6 , u 1 9 , u 2 9 }
] induce a Möbius ladder of length four.

Let G ′ 9 be the graph isomorphic to G 9 . G ′ 9 also consists of ten base subgraphs that are isomorphic to H 0 . For convenience, let H i+10 be the subgraph in G ′ 9 corresponding to H i for 0 ≤ i ≤ 9 and w 10 corresponds to v 0 . Let J ′ be an M L -cover of G ′ 9 isomorphic to J replacing u 1 0 and u 2 0 with u 3 10 and u 4 10 , respectively.

Let G be a graph obtained from G 9 and G ′ 9 by identifying H 0 and H 10 and connecting v 9 and v 19 by a path P with odd order in the sense the path in G connecting v 9 and v 19 not containing u 0 is a path with odd order (see Figure 2.3).

Then the outer walk of G is a cycle and contains every vertex of G. Moreover, every finite face of G is of even length. It means that all cycles of G have even length as well. Hence G is a 2-connected outerplanar bipartite graph. Let K be an M L -cover of G obtained from J and J ′ by identifying J[∪ u∈V (H 0 ) L(u)] and

J ′ [∪ u∈V (H 10 ) L(u)].
We show that G does not admit any M L -colouring. Suppose that G admits an M L -colouring. Let I be an independent set of K with |I| = |G|.

By symmetry, we may assume that either u 1 0 or u 2 0 is in I.

Claim 2.2.2

For each 0 ≤ i ≤ 9, either u 1 i or u 2 i is in I.

Proof. We prove this claim by induction on i. When i = 0, this claim holds. Suppose that i ≥ 1. By Claim 2.2.1 and the induction hypothesis, either v 3 i-1 or v 4 i-1 is in I. Suppose that either u 3 i or u 4 i is in I. Then either w 3 i or w 4 i is in I by Claim 2.2.1. However this contradicts to Lemma 3 since

K[u 1 i-1 , u 2 i-1 , v 3 i-1 , v 4 i-1 , w 3 i , w 4 i , u 3 i , u 4 i ] is isomorphic to a
Möbius ladder of length four. Hence this claim holds.

By Claim 2.2.2, we can deduce a contradiction Lemma 3 since

K[{u 1 0 , u 2 0 , u 1 3 , u 2 3 , u 1 6 , u 2 6 , u 1 9 , u 2 9 }
] is isomorphic to a Möbius ladder of length four.

. The proof of Theorem 53

In this section, we prove our main result Theorem 53 by a technical but stronger result Theorem 54.

We need to introduce more notations so as to state Theorem 54. Let L be a list assignment of G, and let M L and M ′ L be matching assignments over L. We Theorem 54 Let G be a 2-connected outerplanar graph and let C be the outer face of G. Let L be a list assignment of G with |L(u)| ≥ min{deg G (u), 5} for every u ∈ V (G) and let M L be an arbitrary matching assignment over L. Let M 1 L and M 2 L be two arbitrary matching assignments over L in C such that for each u 1 u 2 ∈ E(C),

⋯ ⋯ ⋮ H 0 = H 10 H 1 H 2 H 3 H 9 H 11 H 12 H 13 H 19              odd path
(i) the number of vertices in L(u i ) incident with an edge in M 1 L,u 1 u 2 ∪ M 2 L,u 1 u 2 is at most two for each i ∈ {1, 2}, (ii) if M 1 L,u 1 u 2 ∪ M 2 L,u 1 u 2 ̸ = ∅, then |L(u i )| ≥ min{deg G (u i ) + 1, 5} for each i ∈ {1, 2}, (iii) if there exists a vertex w ∈ L(u i ) incident with three edges in M L,u 1 u 2 ∪ M 1 L,u 1 u 2 ∪ M 2 L,u 1 u 2 , then |L(u 3-i )| ≥ 5, and
(iv) for consecutive three vertices x, y, z on the outer face, if Let us make a few remarks on Theorem 54 before providing the proof.

M 1 L,xy ∪ M 2 L,xy ̸ = ∅ and M 1 L,yz ∪M 2 L,yz ̸ = ∅, then |L(y)| ≥ min{deg G (y)+ 2, 5}. Then G admits an (M L ∪ M 1 L ∪ M 2 L )-colouring unless (G, L, M L ∪ M 1 L ∪ M 2 L ) is bad. ⇒ L(u) L(v) L(u) L(v)
(i) In Theorem 54, M 1 L and M 2 L are two arbitrary matching assignments over L. In fact, it is possible that M 1 L = M 2 L , and we may assume that M 2 L = ∅ in this case.

(ii) We may assume that

(|M L |, |M 1 L |, |M 2 L |
) is as large as possible in lexicographic order. do not satisfy the assumption above since the edge in M 2 L in the left matching assignments can be regarded as an edge in M 1 L , and it increases

(|M L |, |M 1 L |, |M 2 L |).
(iii) We construct a multigraph G m and a matching assignment

M ′ L over L such that G m admits an M ′ L -colouring if and only if G admits an (M L ∪ M 1 L ∪ M 2 L )-colouring.
For every edge e = uv ∈ E(C), we replace e with a multiple edge e ′ such that the multiplicity of e ′ is the number of matching assignments between L(u) and L(v). Note that the number of matching assignments between L(u) and L(v) is unique by remark (ii).

L ∪M 1 L ∪M 2 L as a matching assignment M ′ L of G m over L. Then G m admits an M ′ L -colouring if and only if G admits an (M L ∪ M 1 L ∪ M 2 L )-colouring. ⇒ L(u) L(v) L(w) u v w G u v w G m
L , M 1 L , M 2 L ,
respectively. The number of matching assignments between L(u) and L(v) (resp. L(v) and L(w)) is two (resp. three) and so the multiplicity of uv (resp. Proof. We prove the theorem by induction on the number of faces of G. Suppose that G does not admit any (M L ∪ M 1 L ∪ M 2 L )-colouring. Let G m be a multigraph defined as in remark (iii).

vw) is two (resp. three) in G m . (iv) If M 1 L ∪ M 2 L = ∅ in Theorem 54, then it corresponds to Theorem 53. Since if M 1 L ∪ M 2 L = ∅,

Case 1.

The number of faces of G is two.

In this case, G is a cycle. If |L(v)| = 2 for each v ∈ V (G), we have M 1 L ∪ M 2 L = ∅ by assumption (II), then G admits an (M L ∪ M 1 L ∪ M 2 L )-colouring unless (G, L, M L ∪ M 1 L ∪ M 2 L ) is bad by Theorem 52
(the result of Kim and Ozeki). Hence we may assume that there

exists a vertex v ∈ V (G) with |L(v)| ≥ 3. Then (M L ∪ M 1 L ∪ M 2 L )-cover is isomorphic to neither a t-
(M L ∪ M 1 L ∪ M 2 L )-cover incident with w is at most |L(v)|. By Theorem 52, G m admits an (M L ∪M 1 L ∪M 2 L )-colouring and so G admits an (M L ∪ M 1 L ∪ M 2 L )-colouring. Hence there is a vertex u ∈ V (G) with |L(u)| ≥ 5.

We prove the case by induction on the number of vertices of G.

Suppose that |G| = 3. Write V (G) = {v 1 , v 2 , v 3 } and we may assume that |L(v 1 )| ≥ 5. By assumptions (I) and (II) of Theorem 54, there is

a vertex w 2 ∈ L(v 2 ) incident with at most one edge in the M L,v 1 v 2 ∪ M 1 L,v 1 v 2 ∪M 2 L,v 1 v 2 .
We show that there is a vertex

w 3 ∈ L(v 3 ) not adjacent to w 2 in the (M L ∪ M 1 L ∪ M 2 L )-cover.
Suppose that w 2 is adjacent to every vertex in L(v 3 ). By assumption (II) of Theorem 54, |L(v 3 )| ≥ 3.

Then w 2 is adjacent to three vertices in L(v 3 ). However, by assumption (III) of Theorem 54, |L(v 3 )| ≥ 5 and so there is a vertex w 3 ∈ L(v 3 ) not adjacent to w 2 , a contradiction. Hence there is a vertex

w 3 ∈ L(v 3 ) not adjacent to w 2 in the (M L ∪ M 1 L ∪ M 2 L )-cover. Since |L(v 1 )
| ≥ 5 and w 3 is adjacent to at most three vertices in L(v 1 ), there is a vertex

w 1 ∈ L(v 1 ) adjacent to neither w 2 nor w 3 . Then {w 1 , w 2 , w 3 } is an (M L ∪ M 1 L ∪ M 2 L )-colouring, a contradiction. Suppose that |G| ≥ 4. Recall that we choose u ∈ V (G) with |L(u)| ≥ 5.
Let u 1 and u 2 be the neighbours of u in G and let U i be the subset of L(u i ) such that the degree of each vertex in U i is at least

two in the M L,uu i ∪ M 1 L,uu i ∪ M 2 L,uu i for each i = 1, 2 (see Figure 2.6). Let G ′ := G -u + u 1 u 2 and let L ′ be a list assignment of G ′ such that L ′ (v) = L(v) for every v ∈ V (G ′ ). Let M L ′ , M 1 L ′ , M 2 L ′ be matching assignments over L ′ obtained from M L , M 1 L , M 2
L , respectively, by deleting the edges incident with the vertices in L(u) and adding all

L(u 1 ) L(u) L(u 2 ) L ′ (u 1 ) L ′ (u 2 ) Figure 2.6: The left graph is a part of the (M L ∪ M 1 L ∪ M 2 L )-cover. The right graph is a part of the (M L ′ ∪ M 1 L ′ ∪ M 2 L ′ )-cover. The black vertices are in U 1 and U 2 .
edges between U 1 and U 2 to M L ′ ∪ M 1 L ′ . Note that we do not need to add any edges in

M 2 L ′ since |U i | ≤ 2 for each i ∈ {1, 2}. We show that (G ′ , L ′ , M L ′ ∪M 1 L ′ ∪M 2 L ′ ) is not bad. If U 1 = ∅ or U 2 = ∅, then there is no edge between L ′ (u 1 ) and L ′ (u 2 ). So (G ′ , L ′ , M L ′ ∪ M 1 L ′ ∪ M 2 L ′ ) is not bad. We may assume that U 1 ̸ = ∅ and U 2 ̸ = ∅, so for each i = 1, 2,
we have |L(u i )| ≥ 3 by assumption (II) of Theorem 54 and the definition of U i . For each i = 1, 2, there is a vertex w ∈ L(u i ) such that the degree

of w in M 1 L,u 1 u 2 ∪ M 2 L,u 1 u 2 is zero. Hence (G ′ , L ′ , M L ′ ∪ M 1 L ′ ∪ M 2 L ′ ) is not bad.
By the induction hypothesis, G ′ has an

(M L ′ ∪M 1 L ′ ∪M 2 L ′ )-colouring I ′ . Then I ′ ∩ U 1 = ∅ or I ′ ∩ U 2 = ∅
I ′ ∩ ( L(u 1 ) ∪ L(u 2 )). Then I ′ ∪ {v} is an (M L ∪ M 1 L ∪ M 2 L )-colouring. Case 2.
The number of faces of G is at least three.

Let v 0 , v 1 , . . . , v m+1 be consecutive vertices on the outer face such

that deg G (v i ) = 2 for 1 ≤ i ≤ m, deg G (v 0 ) ≥ 3, and deg G (v m+1 ) ≥ 3; note that v 0 v 1 . . . v m+1 is an ear of G.
Let H be the subgraph of the

(M L ∪ M 1 L ∪ M 2 L )-cover such that V (H) = L(v 0 ) ∪ L(v 1 ) ∪ • • • ∪ L(v m+1 ) and E(H) = 0≤i≤m (M L,v i v i+1 ∪ M 1 L,v i v i+1 ∪ M 2 L,v i v i+1 ). For an integer i with 1 ≤ i ≤ m, we call a pair {a i , b i } of two vertices in L(v i ) a good pair if one of a i and b i is degree at most one in H[ L(v i ) ∪ L(v i+1 )]. Note that
there is a good pair in L(v i ) for every 1 ≤ i ≤ m by assumptions (I) and (II) of Theorem 54. Write

P = v 1 v 2 . . . v m . Let G ′ := G -P and L ′ be a list assignment of G ′ such that L ′ (u) = L(u) for every u ∈ V (G ′ ). Let M L ′ := M L - 0≤i≤m M L,v i v i+1 M 1 L ′ := M 1 L - 0≤i≤m M 1 L,v i v i+1 M 2 L ′ := M 2 L - 0≤i≤m M 2 L,v i v i+1 . Note that |L ′ (v i )| ≥ min{deg G ′ (v i ) + 1, 5} for each i ∈ {0, m + 1} and the edge v 0 v m+1 is on the outer face of G ′ .
We now provide a sketch of our proof of Case 2. We obtain an

(M L ′ ∪ M 1 L ′ ∪ M 2 L ′ )-colouring of G ′
by induction first. We find two independent sets A and B in H consisting of good pairs (Claims 2.3.1). More precisely, independent sets A and B have the property that every pair {a, b} with a ∈ A ∩ L(v j ) and b ∈ B ∩ L(v j ) is a good pair. One of A and B will be a part of an

(M L ∪ M 1 L ∪ M 2 L )-colouring of G.
In order to show that adding one of A and B to an

(M L ′ ∪M 1 L ′ ∪M 2 L ′ )-colouring of G ′ preserves independence, we analyse H[ L(v 0 )∪ L(v 1 )] and H[ L(v m )∪ L(v m+1 )] (
= {b i , b i+1 , . . . , b m } such that (i) a j , b j ∈ L(v j ) for all j such that i ≤ j ≤ m,
(ii) {a j , b j } is a good pair for all j such that i ≤ j ≤ m, and (iii) A and B are independent sets in H.

Proof. We show by induction on j that we can take a j , b j ∈ L(v j ) for each i ≤ j ≤ m such that {a i , a i+1 , . . . , a j } and {b i , b i+1 , . . . , b j } are independent sets in H and a j and b j satisfy conditions (i), (ii), (iii) of the claim. When j = i, the claim holds trivially. So we may assume that j > i. Let A j and B j be subsets of maximum size of L(v j ) such that N H (a j-1 ) ∩ A j = ∅ and N H (b j-1 ) ∩ B j = ∅. We show that we can take a good pair {a j , b j } in L(v j ), which means that we can find a j , b j ∈ L(v j ) such that one of a j and b j has degree at most one in

H[ L(v j ) ∪ L(v j+1 )]
. By induction hypothesis, {a j-1 , b j-1 } is a good pair and so we may assume that a j-1 has degree at most one in

H[ L(v j-1 )∪ L(v j )].

Suppose that the degree of b

j-1 in H[ L(v j-1 ) ∪ L(v j )] is also at most one. If H[ L(v j ) ∪ L(v j+1 )
] is a matching, then we can take any two vertices in L(v j ) as a good pair. There must exist two vertices

a j , b j ∈ L(v j ) with a j-1 a j , b j-1 b j / ∈ E(H) since |L(v j )| ≥ 2.
Hence

H[ L(v j ) ∪ L(v j+1 )] has some edges in M 1 L ∪ M 2 L and |L(v j )| ≥ 3 by assumption (II) of the theorem. If there is no vertex in L(v j ) that is adjacent to both a j-1 and b j-1 , then |A j ∪ B j | = |L(v j )| ≥ 3. If there is a vertex in L(v j ) that is adjacent to both a j-1 and b j-1 , then |L(v j )| ≥ 4 by assumption (IV) of Theorem 54, thus |A j ∪ B j | ≥ |L(v j )| -1 ≥ 3. Hence |A j | ≥ 2, |B j | ≥ 2, and |A j ∪ B j | ≥ 3.
By assumption (I) of the theorem, we can take the desired two vertices to be a j ∈ A j and b j ∈ B j (see the left side of Figure 2.7). Hence we may assume that the degree of b j-1 in H[ L(v j-1 ) ∪ L(v j )] is at least two.

By assumption (II) of the theorem,

|L(v j )| ≥ 3. Note that |A j | ≥ 2 and |B j | ≥ 1. If H[ L(v j ) ∪ L(v j+1 )
] is a matching, then we can take any two vertices in L(v j ) as a good pair, and there exist two vertices

a j , b j ∈ L(v j ) with a j-1 a j , b j-1 b j / ∈ E(H). Hence H[ L(v j ) ∪ L(v j+1 )] has some edges in M 1 L ∪ M 2 L and

Recall that G

′ = G -∪ m i=1 v i , L ′ is the list assignment of G ′ , |L ′ (v i )| ≥ min{deg G ′ (v i ) + 1, 5} for each i ∈ {0, m + 1}, and the edge v 0 v m+1 is on the outer face of G ′ . Claim 2.3.2 One of H[ L(v 0 )∪ L(v 1 )] and H[ L(v m )∪ L(v m+1 )] has some edges in M 1 L ∪ M 2 L .
L(v j-1 )

L(v j ) L(v j+1 ) L(v j-1 ) L(v j ) L(v j+1 ) a j-1 b j-1 a j-1 b j-1 Figure 2.7: The left graph is a part of the (M L ∪ M 1 L ∪ M 2 L )-cover when the case that the degree of b j-1 in H[ L(v j-1 ) ∪ L(v j )]
1 ∈ B satisfying conditions (i)-(iii) of Claim 2.3.1. Write {a m } = A ∩ L(v m ) and {b m } = B ∩ L(v m ). Let c 0 ∈ L(v 0 ) ∩ N H (a 1 ), d 0 ∈ L(v 0 ) ∩ N H (b 1 ), c m+1 ∈ L(v m+1 ) ∩ N H (a m ),
(M L ∪ M 1 L ∪ M 2 L )
-cover is a matching and we add at most two edges between L(v 0 ) and L(v m+1 ). Hence we have

(G ′ , L ′ , M L ′ ∪ M 1 L ′ ∪ M 2 L ′ ) is not bad. It is clear that G ′ satisfies
the assumptions in Theorem 54.

By the induction hypothesis, G

′ has an (M L ′ ∪ M 1 L ′ ∪ M 2 L ′ )-colouring I ′ . If either d 0 ∈ I ′ or d m+1 ∈ I ′ , then I := I ′ ∪ A otherwise I := I ′ ∪ B. Then I is an (M L ∪ M 1 L ∪ M 2 L )-colouring of G. This is a contradiction.
We may assume that

H[ L(v 0 ) ∪ L(v 1 )] has some edges in M 1 L ∪ M 2 L .
Let U 0 and U m+1 be vertex sets such that U i ⊆ L(v i ) and the degree of each vertex in U i is at least two in H for each i ∈ {0, m + 1}. L(v 1 )], there exists a good pair {a 1 , b 1 } of two vertices in L(v 1 ) such that a 1 and b 1 are both not adjacent to u 0 .

Claim 2.3.3 For a vertex u 0 ∈ L(v 0 ) with degree at most one in H[ L(v 0 )∪ L(v 0 ) c 0 d 0 L(v 1 ) a 1 b 1 L(v 2 ) a 2 b 2 L(v 3 ) a 3 b 3 L(v 4 ) c 4 d 4
Proof. If |L(v 1 )| ≥ 4, then there are at least three vertices in L(v 1 ) not adjacent to u 0 and so we can take a good pair by assumption (I). Hence we may assume that |L(v

1 )| = 3. Since H[ L(v 0 )∪ L(v 1 )] has some edges in M 1 L ∪ M 2 L , it follows from assumption (IV) that H[ L(v 1 ) ∪ L(v 2 )
] is a matching. Then we can take a good pair.

Recall that U 0 is the vertex set such that U 0 ⊆ L(v 0 ) and the degree of each vertex in U 0 is at least two in H. For

1 ≤ i ≤ m, if all the vertices in U i-1 are adjacent to the same vertices in L(v i ) and | L(v i ) \ N H (U i-1 )| ≤ 2, then we define U i = L(v i ) \ N H (U i-1 ) (if U i-1 is not
defined, then we do not define U i ). Note that U i ̸ = ∅ by the assumptions (II)-(IV). Let j max be the largest integer j in 0 ≤ j ≤ m such that U jmax is defined. If j max ≥ 1, we take an arbitrary vertex u i from U i for each 0 ≤ i ≤ j max -1 and let U be the set of such vertices (seeFigure 2.9). Since we deal with the case that there is an in H several times after this, we will show a technical claim to handle those situations.

(M L ′′ ∪ M 1 L ′′ ∪ M 2 L ′′ )-colouring I ′ of G ′ such that the degree of the vertex in I ′ ∩ L(v m+1 ) is at most one L(v 0 ) L(v 1 ) L(v 2 ) L(v 3 ) L(v 4 ) L(v 5 ) a 5 b 5 L(v 6 )
Claim 2.3.4 Let L ′′ be a list assignment of G ′ and L ′′ (u) = L(u) for every u ∈ V (G ′ ). Let M L ′′ , M 1 L ′′ , M 2
L ′′ be matching assignments over L ′′ satisfying assumptions (I)-(IV). Suppose that there is an

(M L ′′ ∪M 1 L ′′ ∪ M 2 L ′′ )-colouring I ′ of G ′ such that the degree of the vertex in I ′ ∩ L(v m+1
) is at most one in H. Then the following properties hold.

(i) The degree of the vertex in I ′ ∩ L(v 0 ) is at least two in H.

I ′ ∩ L(v m+1 ). Then I ′ ∪ A is an (M L ∪ M 1 L ∪ M 2 L )-colouring of G, a contradiction.
(ii) Suppose that j max ≤ m -1. We prove the following subclaim.

Subclaim 2.3.4.1

For any good pair {a j max +1 , b j max +1 } of two vertices in L(v j max +1 ), either a j max +1 or b j max +1 is adjacent to every vertex in U j max .

By assumption (IV), H[ L(v jmax+1 ) ∪ L(v jmax+2 )] is a matching and so every pair of two vertices in L(v jmax+1 ) is a good pair. Hence we can take a good pair {a jmax+1 , b jmax+1 } of two vertices in L(v jmax+1 ) such that both a jmax+1 and b jmax+1 are not adjacent to one of the vertices in U jmax .

This contradicts Subclaim 2.3.4.1.

Claim 2.3.5 Both H[ L(v 0 )∪ L(v 1 )] and H[ L(v m )∪ L(v m+1 )] have some edges in M 1 L ∪ M 2 L . Proof. Suppose that H[ L(v m ) ∪ L(v m+1 )] has no edges in M 1 L ∪ M 2 L . By Claim 2.3.2, H[ L(v 0 ) ∪ L(v 1 )] has some edges in M 1 L ∪ M 2 L . Subclaim 2.3.5.1 |L(v 0 )| ≥ 5.
Proof. Suppose that |L(v 0 )| ≤ 4. By the assumption (II) of Theorem 54, Suppose that Since

deg G (v 0 ) ≥ 3 and we obtain deg G (v 0 ) = 3 and deg G ′ (v 0 ) = 2. Let L ′′ be a list assignment of G ′ such that L ′′ (u) =      L ′ (u) -{c ∈ L(u) : (u, c) ∈ U 0 }, if u = v 0 , L ′ (u), otherwise. Let M L ′′ , M 1 L ′′ , M 2 L ′′ be matching assignments over L ′′ obtained from M L ′ , M 1 L ′ , M 2 L ′ ,
(G ′ , L ′′ , M L ′′ ∪ M 1 L ′′ ∪ M 2 L ′′ ) is bad, then the (M L ′′ ∪ M 1 L ′′ ∪ M 2 L ′′ )-cover of G ′ must
|L ′′ (v m+1 )| ≥ 3, the (M L ′′ ∪ M 1 L ′′ ∪ M 2 L ′′ )-cover of G ′ is not
isomorphic to a ladder of odd length or a Möbius ladder of even length,

a contradiction. Hence (G ′ , L ′′ , M L ′′ ∪ M 1 L ′′ ∪ M 2 L ′′ ) is not bad. By the induction hypothesis, G ′ has an (M L ′′ ∪M 1 L ′′ ∪M 2 L ′′ )-colouring I ′ . Since the vertices in I ′ ∩ ( L(v 0 ) ∪ L(v m+1
)) are degree at most one in H, this contradicts Claim 2.3.4 (i). Hence the subclaim holds.

Since

H[ L(v m ) ∪ L(v m+1 )] is a matching, it follows from Claim 2.3.4 (ii) that we obtain j max = m. Suppose that |U m | ≥ 2. Since H[ L(v m ) ∪ L(v m+1 )] is a matching, one of the vertices in U m , say u m , is not adjacent to the vertex in I ′ ∩ L(v m+1 ). Then I ′ ∪ U ∪ {u m } is an (M L ∪ M 1 L ∪ M 2
L )-colouring of G. This is a contradiction. Hence |U m | = 1 and write U m = {u m }. Let w m+1 be the vertex in L(v m+1 ) adjacent to u m . We add the edges between U 0 and w m+1 to

M 1 L ′ ∪ M 2 L ′ . Since |L(v 0 )| ≥ 5, such new M L ′ , M 1 L ′ , M 2
L ′ satisfy the assumptions of Theorem 54 and

(G ′ , L ′ , M L ′ ∪M 1 L ′ ∪M 2 L ′ ) is not bad. By the induction hypothesis, G ′ has an (M L ′ ∪ M 1 L ′ ∪ M 2 L ′ )-colouring I ′′ . By Claim 2.3.4 (i), I ′′ ∩ U 0 ̸ = ∅ and so w m+1 / ∈ I ′′ . However I ′′ ∪ U ∪ {u m } is an (M L ∪ M 1 L ∪ M 2 L )-colouring of G, a contradiction. Claim 2.3.6 |L(v 0 )| ≥ 5 and |L(v m+1 )| ≥ 5. Proof. Suppose that one of |L(v 0 )| and |L(v m+1 )| is at most four. We may assume that |L(v m+1 )| ≤ 4. Let L ′′ be a list assignment of G ′ such that L ′′ (u) =      L ′ (u) -{c ∈ L ′ (u) : (u, c) ∈ U m+1 } if u = v m+1 L ′ (u) otherwise. Let M L ′′ , M 1 L ′′ , M 2 L ′′ be matching assignments over L ′′ obtained from M L ′′ , M 1 L ′′ , M 2
L ′′ , respectively, by deleting the edges incident with the vertices in U m+1 . We have

2 ≤ |L ′′ (v m+1 )| ≤ 3, |L ′′ (v 0 )| ≥ 4
, and the graph induced by the edges connecting L ′′ (v 0 ) and

L ′′ (v m+1 ) is a matching. Hence, (G ′ , L ′′ , M L ′′ ∪ M 1 L ′′ ∪ M 2 L ′′ )
is not bad and satisfies the assumptions of the theorem. By the induction hypothesis,

G ′ has an (M L ′′ ∪ M 1 L ′′ ∪ M 2 L ′′ )-colouring I ′ . Since the vertex in I ′ ∩ L(v m+1
) is degree one in H, it follows from Claim 2.3.4 (ii) that we obtain j max = m.

We show that |U m | ≥ 2. By Claim 2.3.5 and assumption (II) of the

theorem, |L(v m )| ≥ 3. If |L(v m )| = 4, then |N H (U m-1 ) ∩ L(v m )| ≤ 2 by assumption (III) of the theorem and so |U m | ≥ 2. If |L(v m )| ≥ 5, then |N H (U m-1 ) ∩ L(v m )| ≤ 3 and so |U m | ≥ 2. Suppose that |L(v m )| = 3. By Claim 2.3.

and assumption (IV) of the theorem, |N

H (U m-1 )∩ L(v m )| = 1 and so |U m | ≥ 2. Hence |U m | ≥ 2. This together with I ′ ∩ U m+1 = ∅
implies that there is a vertex u m in U m not adjacent to the vertex in

I ′ ∩ L(v m+1 ). Then I ′ ∪ U ∪ {u m } is an (M L ∪ M 1 L ∪ M 2 L )-colouring of G. This is a contradiction.
We add the edges between U 0 and U m+1 to

M 1 L ′ ∪ M 2 L ′ . By Claim 2.3.6 and assumption (I) of Theorem 54, (G ′ , L ′ , M L ′ ∪M 1 L ′ ∪M 2 L ′ )
is not bad and satisfies the assumptions of Theorem 54. By the induction hypothesis, G ′ has an

(M L ′ ∪ M 1 L ′ ∪ M 2 L ′ )-colouring I ′ . Note that either U 0 ∩I ′ = ∅ or U m+1 ∩I ′ = ∅. We may assume that U 0 ∩I ′ = ∅.
Suppose that m = 1. By Claim 2.3.5 and assumption (IV) of

Theorem 54, |L(v 1 )| ≥ 4. Since U 0 ∩ I ′ = ∅, there is at most one vertex in L(v 1 ) adjacent to the vertex in I ′ ∩ L(v 0 ). If |L(v 1 )| = 4, then there are at most two vertices in L(v 1 ) adjacent to the vertex in I ′ ∩ L(v m+1 ).
If |L(v 1 )| ≥ 5, then there are at most three vertices in L(v 1 ) adjacent to the vertex in I ′ ∩ L(v m+1 ). In the both cases, there is at least one vertex in L(v 1 ) not adjacent to I ′ ∩ ( L(v 0 ) ∪ L(v m+1 )). Then we add such a vertex to I ′ and it is an

(M L ∪ M 1 L ∪ M 2 L )-colouring of G. This is a contradiction. Hence m ≥ 2.
We show that there exists a good pair {a 1 , b 1 } of two vertices in L(v 1 ) such that a 1 and b 1 are not adjacent to

I ′ ∩ L(v 0 ). If |L(v 1 )| ≥ 4, then since U 0 ∩ I ′ = ∅,
m-1 , say a m-1 , is not adjacent to u m . Then I ′ ∪ {u m }∪(A\{a m }) is an (M L ∪M 1 L ∪M 2 L )-colouring of G, a contradiction. Hence |L(v m )| ≥ 4. By condition (ii) of Claim 2.3.1, one of a m-1 and b m-1 , say a m-1 , is degree one in H[ L(v m-1 )∪ L(v m )]. If |L(v m )| = 4,
I ′ ∩ L(v m+1 ) ∪ {a m-1 }. Then I ′ ∪ {w m } ∪ (A \ {a m }) is an (M L ∪ M 1 L ∪ M 2 L )-colouring of G, a contradiction. So we complete
the proof of Theorem 54.

-Beyond the fractional Reed bound for triangle-free graphs

Given a graph H, we let χ f (d, H) be the supremum of the fractional chromatic numbers over all H-free graphs of maximum degree at most d. In this chapter, we study χ f (4, K 3 ).

. Introduction

When H is a complete graph, the study of χ f (d, H) falls in the domain of Ramsey theory, a domain which emerged in the 1930s following seminal results by van der Waerden [START_REF] Van Der Waerden | Beweis einer Baudetschen Vermutung[END_REF] and by Ramsey [START_REF] Ramsey | On a problem of formal logic[END_REF], and has attracted a lot of attention ever

since. An important result in this case is due to Molloy and Reed [82, Theorem

: known as "the fractional Reed bound", it states that

χ f (d, K n ) ≤ d+n 2 for all integers d, n ≥ 2.
In this chapter, we focus on the case H = K 3 , which is closely related to off-diagonal Ramsey numbers. It has been established [START_REF] Dvořák | Subcubic triangle-free graphs have fractional chromatic number at most 14/5[END_REF] that χ f (3, K 3 ) = 14/5.

The same question for larger values of the maximum degree is still open. At one end of the spectrum, we know that χ f (4, K 3 ) lies between 3.25 (see Figure 3.1) and 3.5 (by the fractional Reed bound). At the other end of the spectrum, one

has χ f (d, K 3 ) ≤ (1 + o(1)) d/ ln d as d → ∞,
which is a consequence of a result by Molloy [START_REF] Molloy | The list chromatic number of graphs with small clique number[END_REF], and one can infer from a study of random d-regular graphs by Bollobás [13] help of a so-called greedy fractional colouring algorithm (GFCA). This algorithm takes as input a graph G and a probability distribution π on the independent sets of any induced subgraph of G, and returns a fractional colouring of G whose weight is bounded by a function of π and G. They proved the following.

that χ f (d, K 3 ) ≥ d 2 ln d . A first study of χ f (d, K 3 )
Theorem 55 [START_REF] Pirot | Fractional chromatic number, maximum degree, and girth[END_REF] For every integer d,

χ f (d, K 3 ) ≤ 1 + min k∈N inf λ>0 (1 + λ) k + λ(1 + λ)d λ(1 + kλ) .
The upper bound in Theorem 55 which can be effectively computed from this formula improves on the fractional Reed bound as soon as d ≥ 17. When d ∈ [START_REF]Problem Garden[END_REF][START_REF] Borodin | Problems of colouring and of covering the vertex set of a graph by induced subgraphs[END_REF], the bound still follows d+3 2 . We use the GFCA to obtain the following result.

Theorem 56 χ f (4, K 3 ) < 3.4663.

. Notations

Let G be a given graph. If J is a subset of vertices of G, then we write N G (J) for the set of vertices that are not in J and have a neighbour in J, while N G [J] is N G (J)∪J. We omit the graph subscript when there is no ambiguity, write N (v)

for N ({v}), and we sometimes write N X (v) instead of N (v) ∩ X, for any subset of vertices X ⊆ V (G). As mentioned earlier, the set of all independent sets of G

is I (G). If w is a mapping from I (G) to R, then for every vertex v ∈ V (G) we set w[v] := I∈I (G) v∈I w(I).
Further, if I is a collection of independent sets of G, then w(I ) := I∈I w(I).

If I is an independent set of a graph G, a vertex v is covered by I if v belongs to I
or has a neighbour in I. A vertex that is not covered by I is uncovered (by I).

. Intuition of our method

In order to apply the GFCA to a graph G, one needs to have some probability distribution over the independent sets of any given induced subgraph H of G.

When this probability distribution has a relatively uniform coverage of the closed neighbourhoods in H -this is referred to as (α, β)-local occupancy in works using the GFCA -one can deduce an upper bound on the fractional chromatic number of G.

In previous works using the GFCA, the input probability distribution has always been the hard-core distribution on some family of independent sets of H. In this paper, we construct our random independent sets in several steps, where at each step we lie within the subgraph of H induced by the vertices uncovered by the random independent set constructed so far. The first step is the hard-core distribution with fugacity λ, and the last step is given by a specific fractional colouring with local demand (the demand is a decreasing function of the degree).

. Prerequisites

In this section we introduce the notions that will be needed to derive our results.

. Greedy fractional colouring algorithm

Our results on fractional colouring are obtained using a greedy algorithm analysed in a recent work [START_REF] Davies | Coloring triangle-free graphs with local list sizes[END_REF]. This algorithm is a generalisation of an algorithm first described in the book of Molloy and Reed [82, p. 245] for the uniform distribution over maximum independent sets. The setting here is, for each induced subgraph H of the graph we wish to fractionally colour, a probability distribution over the independent sets of H.

Lemma 3 [START_REF] Davies | Coloring triangle-free graphs with local list sizes[END_REF] Let G be a graph given with couples (α v , β v ) for every vertex v ∈ V (G). For every induced subgraph H of G, let I H be a random independent set of H drawn according to a given probability distribution, and assume that

α v P [v ∈ I H ] + β v E [|I H ∩ N (v)|] ≥ 1,
for every v ∈ V (H). Then the GFCA produces a fractional colouring w of G which certifies that

χ f (G) ≤ max v∈V (G) α v + β v deg(v).
Algorithm 1: The Greedy Fractional Colouring Algorithm (GFCA)

for I ∈ I (G) do w(I) ← 0 H ← G while |V (H)| > 0 do ι ← min v∈V (H) 1 -w[v] P [v ∈ I H ] for I ∈ I (H) do w(I) ← w(I) + P [I H = I] ι H ← H -{v ∈ V (H) : w[v] = 1}
We note that in Lemma 3, although there is one probability distribution on each induced subgraph, the couple (α v , β v ) associated with each vertex is fixed once and for all, which somewhat ties together the different probability distributions involved.

In our setting (the class of triangle-free graphs of bounded degree), the only way to distinguish vertices when we look only at their first neighbourhood is by considering their degree (and possibly those of their neighbours). In particular, if G is a regular graph, then there I s no way of distinguishing its vertices in our setting.

For that reason, we will only apply Lemma 3 with all couples (α v , β v ) v∈V (G) equal.

To ensure optimality, our task is to solve the following linear program.

Definition 13.

Let G be a graph, and let φ map each (induced) subgraph H ⊆ G to a random independent set φ(H) ∈ I (H). We let LP φ (G), which we call the linear program associated with (G, φ), be defined as follows.

LP φ (G) :

                   Minimise α + β∆ such that α P [v ∈ φ(H)] + β E [|φ(H) ∩ N (v)|] ≥ 1, for all H ⊆ G v ∈ V (H); α, β ≥ 0.
First, we need to compute the constraints of the linear program described above. To that end, we define the following. Definition 14. Let H be a graph and I a random independent set of H. For every vertex v ∈ V (H), we let

e I (v) :=   P [v ∈ I] E [|N (v) ∩ I|]   be the constraint of I on v.
With the above definition in hand, the constraints of the linear program are all of the form (α, β)

• e φ(H) (v) ≥ 1, for every H ⊆ G and v ∈ V (H).
We note that if we generate the whole set of constraints {e φ(H) (v) : H ⊆ G, v ∈ V (H)}, we may end up with a huge number of constraints. It is however possible to considerably reduce the number of constraints by restricting to a specific subset. This requires the introduction of a partial ordering on the set of constraints.

In the end, we will keep only minimal constraints with respect to that order, and argue that this does not affect the result of the linear program. Definition 15. Given two constraints e 0 = (p 0 , q 0 ) T and e 1 = (p 1 , q 1 ) T , we say that e 0 is tighter than e 1 , or equivalently that e 1 is looser then e 0 , if they satisfy p 0 ≤ p 1 and p 0 + q 0 ≤ p 1 + q 1 . We denote it e 0 ≾ e 1 .

We can now introduce a new linear program obtained by keeping only minimal constraints with respect to (≾) from the complete linear program.

Definition 16.

Let G be a graph, and let φ map each (induced) subgraph H ⊆ G to a random independent set φ(H) ∈ I (H). We denote E φ the set of minimal constraints with respect to (≾)

among {e φ(H) (v) : H ⊆ G, v ∈ V (H)}. We let LP * φ (G, φ
), which we call the reduced linear program associated with (G, φ), be defined as follows.

LP * φ (G) :                    Minimise α + β∆ such that αp + βq ≥ 1, for each    p q    ∈ E φ ; α, β ≥ 0.
We now argue that solving LP * φ (G) instead of LP φ (G) is enough for our purpose. This is justified by the following claim. Proof. Let (α, β) realise the solution of the linear program LP * φ (G), which we assume to be at most ∆ + 1. So, in particular, the constraint generated by a subgraph H = {v} of G must be satisfied, i.e. α ≥ 1.

If we now assume for the sake of contradiction that β > α, then the solution of the linear program will be more than ∆(G) + 1, which contradicts the assumption. So we have α ≥ β. We now argue that

every constraint e I H (v) = (x, y) T for H ⊆ G and v ∈ V (H) is satisfied.
Indeed, there is a constraint e ′ = (x ′ , y ′ ) T that is minimal with respect to (≾) and such that e ′ ≾ e I H (v). The constraint e ′ appears in the linear program, so it is satisfied by assumption; we have αx ′ + βy ′ ≥ 1. So we

have αx + βy = (α -β)x + β(x + y) ≥ (α -β)x ′ + β(x ′ + y ′ ) = αx ′ + βy ′ ≥ 1.
This ends the proof.

. Hard-core model

The probability distribution that we are going to use as a setting of Lemma 3 uses the hard-core distribution over the independent sets of a graph, which has the Spatial Markov Property. Given a family I of independent sets of a graph H, and a positive real λ, a random independent set I drawn according to the hard-core distribution at fugacity λ over I is such that Note that when I = I (H), and λ → ∞, the hard-core distribution converges towards the uniform distribution over the maximum independent sets of H.

P [I = I] = λ |I| Z I (λ) ,
Lemma 4 (Spatial Markov Property) Given a graph H, and a real λ > 0, let I be drawn according to the hard-core distribution at fugacity λ over the independent sets I (H) of H. Let X ⊆ V (H) be any given subset of vertices, and J be any possible outcome of I \ X. Then, conditioned on the fact that I\X = J, the random independent set I∩X follows the hard-core distribution at fugacity λ over the independent sets of H[X \ N (J)].

Proof. Conditioned on the fact that I \ X = J, let I J be the set of possible realisations of I ∩ X. Now, for every I ∈ I J ,

P [I ∩ X = I | I \ X = J] = P [I = I ∪ J] = λ |I∪J| I ′ ∈I J λ |I ′ ∪J| = λ |I| I ′ ∈I J λ |I ′ | • λ |J| λ |J| = λ |I| I ′ ∈I J λ |I ′ | = λ |I| Z I J (λ)
.

The proof of this result is standard and follows from a simple consideration of the marginal probabilities. It remains valid when we fix λ = ∞, i.e. the uniform distribution over the maximum independent sets of any graph H has the Spatial Markov Property.

Among the many consequences of the Spatial Markov Property, one can observe that for every vertex v ∈ V (H),

P [v ∈ I] = λ P [v is uncovered by I] .
(3.1)

. Maximum degree 4

In this section, we focus on optimising the upper bound of χ f (4, K 3 ). To that end, we use a 2-step procedure to construct the random independent sets that feed the GFCA. The first step follows the hard-core distribution, and the second step consists of a fractional colouring with local demand of the uncovered vertices of degree at most 4. Before describing the procedure in more detail, we introduce the necessary terminology. Let G be a graph. Given a function f :

V (G) → Q + , an f -fractional colouring of G is a random independent set I of G such that P [v ∈ I] ≥ f (v) for every vertex v ∈ V (G). An f -fractional colouring of G is also called a fractional colouring of G with local demand f . Given a vertex v, the value of f (v) is called the demand of v.
We say that a subgraph H of a given subcubic graph G is dangerous if it is isomorphic to C 5 or to K + 4 (the complete graph on 4 vertices where two non-adjacent edges have been subdivided twice each, see Figure 3 In order to analyse the final step of our procedure, we use the following result [START_REF] Dvořák | Subcubic triangle-free graphs have fractional chromatic number at most 14/5[END_REF].

Theorem 57 [START_REF] Dvořák | Subcubic triangle-free graphs have fractional chromatic number at most 14/5[END_REF][START_REF] Dvořák | Subcubic triangle-free graphs have fractional chromatic number at most 14/5[END_REF] Let G be a triangle-free subcubic graph, and let B be a nail of G. For every vertex v ∈ B, we let f B (v) = 7-deg(v)

14

, and for every vertex v / ∈ B, we let f B (v) = 8-deg(v)

14

.

Definition 18. For every H ∈ dom(φ) and v ∈ V (H), we let

e + φ,H (v) :=       P [v ∈ φ(H)] E [|N (v) ∩ φ(H)|] u∈N H (v) µ φ (deg H (u) -1)      
be the refined constraint of φ on v.

We extend the order (≾) to refined constraints as follows.

Definition 19. Given two refined constraints e 0 = (p 0 , q 0 , r 0 ) T and e 1 = (p 1 , q 1 , r 1 ) T , we say that e 0 is tighter than e 1 , or equivalently that e 1 is looser then e 0 , if they satisfy p 0 ≤ p 1 , p 0 + q 0 ≤ p 1 + q 1 , and r 0 ≤ r 1 . We denote it e 0 ≾ e 1 .

For every integer d ≤ ∆(G), we denote E + φ (d) the set of minimal refined constraints in

e + φ,H (v) : H ∈ dom(φ), v ∈ V (H), deg H (v) = d ,
with respect to (≾). We now show how to rely on this set of refined constraints in order to compute a random independent set constructed in two steps as follows.

Lemma 5 Let G be a triangle-free graph. Let I be a random independent set of G constructed in two steps, i.e. I = I 0 ∪ φ(G \ N [I 0 ]), where I 0 is drawn from the hard-code distribution at fugacity λ > 0 from I (G), and φ maps any subgraph H ⊆ G to a random independent set of H. Then each constraint e I (v) is looser than some convex combination of the vectors

       1 λ + (1 + λ) d λ + p (1 + λ) d-1 (dλ + r) + q -r : d ∈ {0, 1, . . . , ∆(G)} and     p q r     ∈ E + φ (d)        .
Proof. Given a possible realisation

J of I 0 \ N [v], let E J be
P [u ∈ I 0 | E J ] = λ(1 + λ) d-1 λ + (1 + λ) d for every u ∈ N (v) \ N (J).
If we further condition on the event that v is uncovered by I 0 , then we have I 0 = J. Let us write this event E 0 J ; we have

P [E 0 J | E J ] = 1 λ+(1+λ) d . If we write H 1 = G \ N [J], then the fact that E 0 J holds means that G\N [I 0 ] = H 1 . Note that we have v ∈ V (H 1 ), and deg H 1 (v) = d. So there exists      p q r      ∈ E + φ (d) such that      p q r      ≾ e + φ,H 1 (v) =      p ′ q ′ r ′     
. It follows that

P v ∈ I 1 | E 0 J = P [v ∈ φ(H 1
)] = p ′ , and so

P [v ∈ I | E J ] = P [v ∈ I 0 | E J ] + P v ∈ I 1 E 0 J P E 0 J E J = λ λ + (1 + λ) d + p ′ λ + (1 + λ) d ≥ λ + p λ + (1 + λ) d . (3.2)
We now let E * J be the random event that N (v) ∩ I 0 ̸ = ∅, given the event E J . Observe that E J ≡ E 0 J ∨ E * J ∨ "v ∈ I 0 ", and that P [u ∈ V (G \ N [I 0 ])] equals 0 under the event "v ∈ I 0 " and 1 under the event E 0 J . We have

P [u ∈ V (G \ N [I 0 ]) | E J ] = 1 1 + λ (1 -P [v ∈ I 0 | E J ]) = (1 + λ) d-1 λ + (1 + λ) d ,
and so

P [u ∈ V (G \ N [I 0 ]) ∧ E * J | E J ] = P [u ∈ V (G \ N [I 0 ]) | E J ] -P E 0 J E J = (1 + λ) d-1 -1 λ + (1 + λ) d . If H ′ 1 is any realisation of G \ N [I 0 ] under the condition E * J , then deg H ′ 1 (u) ≤ deg H 1 (u) -1 for every u ∈ N (v) ∩ V (H ′ 1 ), since v / ∈ V (H ′ 1 ). In particular, P [u ∈ φ(H ′ 1 )] ≥ µ φ deg H 1 (u) -1 . It follows that P [u ∈ I 1 ∧ E * J | E J ] ≥ P [u ∈ V (G \ N [I 0 ]) ∧ E * J | E J ] µ φ deg H 1 (u) -1 ≥ (1 + λ) d-1 -1 λ + (1 + λ) d µ φ deg H 1 (u) -1 ,
and so

P [u ∈ I 1 | E J ] = P [u ∈ I 1 ∧ E * J | E J ] + P u ∈ I 1 E 0 J P E 0 J E J ≥ 1 λ + (1 + λ) d ((1 + λ) d-1 -1)µ φ deg H 1 (u) -1 + P [u ∈ φ(H 1 )] .
We now infer that

E |N (v) ∩ I| E J = u∈N H 1 (v) (P [u ∈ I 0 | E J ] + P [u ∈ I 1 | E J ]) ≥ dλ(1 + λ) d-1 λ + (1 + λ) d + u∈N H 1 (v) 1 λ + (1 + λ) d ((1 + λ) d-1 -1)µ φ deg H1 (u) -1 + P [u ∈ φ(H 1 )] .

So we have

P [v ∈ I | E J ] + E |N (v) ∩ I| E J ≥ λ + p ′ λ + (1 + λ) d + dλ(1 + λ) d-1 λ + (1 + λ) d + u∈N H 1 (v) 1 λ + (1 + λ) d ((1 + λ) d-1 -1)µ φ deg H1 (u) -1 + P [u ∈ φ(H 1 )] ≥ λ + p + (1 + λ) d-1 (dλ + r) + q -r λ + (1 + λ) d . ( 3.3)
We finish the proof with the laws of total probability and expectation, from which we infer that the constraint e I (v) is looser than some convex combination of the vector formed with the right-hand sides of (3.2) and (3.3).

Now, we need to compute the sets E + φ (d) for each integer d ≤ 4, where φ is the finishing step described in Section 3.3.1.

Lemma 6

If G is a triangle-free graph of maximum degree at most 4, and φ maps each subgraph H of G to the f H -fractional colouring given by Corollary 3, then we have

µ φ (0) = 1, µ φ (1) = 1/2, µ φ (2) = 11/28, µ φ (3) = 5/14, µ φ (4) = 0; E + φ (0) =            1 0 0            ; E + φ (1) =            1/2 1/2 1     ,     4/7 3/7 1/2     ,     9/14 5/14 11/28     ,     1 0 5/14            ; E + φ (2) =            11/28 3/4 25/28     ,     3/7 5/7 11/14     ,     1/2 1/2 19/14     ,     4/7 3/7 6/7     ,     9/14 5/14 3/4     ,     1 0 5/7            ; E + φ (3) =           
    ,     1 0 15/14            ; E + φ (4) =            0 0 10/7            .
Proof. The values of µ φ (d) for each d ≤ 4 follow readily from the definition of f H .

Computing E +

φ (1) is straightforward: given a vertex v ∈ V (H) of degree 1, its unique neighbour u has degree deg H (u) ∈ {1, . . . , 4}. By definition of f H , the constraint in v is of the form

     1 -f H (u) f H (u) µ φ (deg H (u) -1)      .
When the degree of u is fixed, the worst case is when f H (u) is maximised (since this decreases the demand for v); hence for the case deg H (u) = 2 we keep the value f H (u) = 3/7.

To compute E + φ (2), we can first reuse E + φ (1) to treat the case where the root vertex v has (at least) one neighbour u of degree 4, by adding 5/14 to the last coordinate of the constraint associated to the pattern obtained by removing u. Note that this can be done more generally for every degree. There remains to consider the patterns where both neighbours u 1 , u 2 of v have degree at most 3. The minimum total demand of the neighbourhood (i.e. the second coordinate of the constraint) is 5/7 and is reached when both u 1 and u 2 have degree 3, but in that case v cannot be special and so its demand is 3/7; this yields the constraint (3/7, 5/7, 11/14) T . The minimum demand for v is µ φ (2) = 11/28 and is reached when v is special; in that case it must have a special neighbour of demand 11/28, and in the worst case its other neighbour has degree 3 and demand 5/14. This yields the constraint (11/28, 3/4, 25/28) T .

To compute E + φ (3), we reuse E + φ (2) as explained above, and then consider the patterns where all neighbours of v have degree at most 3. The minimum demand for v is µ φ (3) = 5/14, and the minimum total demand for its neighbourhood is 3µ φ (3) = 15/14; this is reached when all its neighbours have degree 3. This yields the constraint ( 5 14 , 15 14 , 33 28 ) T . To compute E + φ (4), the worst case is when v has four degree-4 neighbours, which yields the constraint e 0 = (0, 0, 10 7 ) T . Note that e 0 is tighter than all constraints that could be inherited from E + φ (3), so these are discarded from E + φ (4) (since we keep only minimal constraints with respect to (≾)).

In Figure 3.3, we present the patterns rooted in a degree-3 vertex yielding the refined constraints in E + φ (3)

. Giving non-zero demand to (some) degree-4 vertices

Let H be any subgraph of G (which we recall is a triangle-free graph of maximum degree 4). Let S ≤3 ⊆ V (H) be the set of vertices of degree at most 3, and let S 4 = V (H) \ S ≤3 be the set of vertices of degree 4. We further partition Let X be the random set promised by Claim 3.3.1, so that H ′ := H \ X is a (random) subcubic triangle-free graph. We are now ready to define the new finishing step.

S 4 into S 0 4 ∪ S + 4 ,
Let φ ′ : H → φ(H ′ ) for every H ⊆ G, where φ is the finishing step described in Section 3.3.3. Let us analyse the constraints that it generates.

For every vertex v ∈ S 4 , we have

P v ∈ φ ′ (H) ≥ E [µ φ (deg H ′ (v)) | v / ∈ X] P [v / ∈ X] ,
and

E |N (v) ∩ φ ′ (H)| ≥ u∈N (v) E [µ φ (deg H ′ (u)) | u / ∈ X] P [u / ∈ X] .
For every v ∈ S 0 4 , every neighbour of v has degree at most 3 in H and belongs to V (H ′ ). Since we always have v / ∈ V (H ′ ), we infer that deg H ′ (u) ≤ 2 for every u ∈ N (v). Since µ φ (2) ≥ 11/28, we conclude that (0, 11/7, 11/7) T ≾ e + φ ′ ,H (v).

For every v ∈ S + 4 , we have

E [µ φ (deg H ′ (v)) | v / ∈ X] ≥ µ φ (3) ≥ 5 14 ,
and so

P v ∈ φ ′ (H) ≥ 5 28 .
(3.4)

Since moreover all degree-4 neighbours of v are also in S + 4 , (3.4) holds for them as well; hence

E |N (v) ∩ φ ′ (H)| ≥ 4 × 5 28 = 5 7 .
We recall that µ φ (3) ≥ 5/14, so we conclude that (5/28, 5/7, 10/7) T ≾ e + φ ′ ,H (v).

The two constraints that we have derived are reached by the patterns drawn in Figure 3.4. We conclude that Proof. This is straightforward once one notices that, by definition of φ ′ , where I 0 ← hc λ (H). We construct the linear program LP * φ 0 (G) with the set of constraints depicted in Table 3.1, which we obtain by combining Lemma 5 with the values of E + φ ′ (d) computed above. The solution to that program is reached when α = 1.8980861 and β = 0.39205135; this implies that χ f (4, K 3 ) < 3.4663.

E + φ ′ (4) =               0 11/7 11/7      ,      5/28 5/7 10/7               . v v ∈ X e I H (v) =   0 11/7   v if v ∈ X if v / ∈ X e I H (v) =   0 5/14   e I H (v) =   5
e + φ ′ ,H (v) = E e + φ,H ′ (v) . v u 1 if u 1 ∈ X if u 1 / ∈ X e I H (v) =   3
E φ0 (0) = 1 0 ; E φ0 (1) = 1/2 1/2 ; E φ0 (2)
(G) ≥ n + k 1 k 2 -2 with k 1 , k 2 ≥ 2, then G is (k 1 , k 2 )-Hamilton-connected. Moreover, the bound of σ 2 (G) is sharp.
We construct a graph G of order n certifying the sharpness of Theorem 59.

For any

k 1 , k 2 ≥ 2 and n = k 1 k 2 + k 1 + k 2 -1, G consists of G 1 = K k 1 , G 2 = K k 1 k 2 -1 , and G 3 = K k 2 such that each vertex of G 1 is adjacent to each vertex of G 2 and each vertex of G 3 is adjacent to each vertex of G 2 . We have σ 2 (G) = n + k 1 k 2 -3. But for X = V (G 1 ) and U = V (G 3 ),

. Proof of Theorem 58

For the purpose of proof, we need the following preliminaries. In fact, the following notations and terminology are also suitable for the proof of Theorem 59.

Let G be a graph. For two disjoint vertex subsets X = {x 1 , x 2 , . . . , x k 1 } and

U = {u 1 , u 2 , . . . , u k 2 } with k 1 , k 2 ≥ 2, an (X, U )-connection of G is a set of k 1 k 2 internally-disjoint paths S i,j connecting x i to u j for 1 ≤ i ≤ k 1 and 1 ≤ j ≤ k 2 . Specially, we call G is (k 1 , k 2 )-connected if for every k 1 -subset X of V (G) and k 2 -subset U of V (G)\{X}, G contains an (X, U )-connection as a subgraph. If an (X, U )-connection spans G, then it is a spanning (X, U )-connection of G.
Let the orientation of S i,j be from x i to u j . For any subset W of V (S i,j ), we use W -(or W + ) to denote the set of predecessors (or successors) of W in S i,j , respectively.

For any vertex v ∈ V (S i,j ), we use v -(or v + ) to denote the predecessor (or successor) of v in S i,j , respectively. For the endpoints of S i,j , it has either no predecessor or no successor.

The following lemma is also necessary for the proof. be the path connecting y to u j for 2 ≤ j ≤ k. Let F be a subgraph of G consisting of all these 2k -1 paths. Assume that the order of F is minimal, denoted by assumption (I).

Lemma 7 ([71])

Let P = u 1 u 2 u 3 • • • u p be a path in a graph G. Let w 1 and w 2 be two vertices in V (G) \ V (P ) such that (N G (w 1 ) ∩ (V (P ) \ {u 1 })) -∩ N G (w 2 ) = ∅. Then |N G (w 1 ) ∩ V (P )| + |N G (w 2 ) ∩ V (P )| ≤ p + 1. Moreover, if |N G (w 1 ) ∩ V (P )| + |N G (w 2 ) ∩ V (P )| = p + 1, then w 1 u 1 , w 2 u p ∈ E(G). 4.2.1 . The graph is (2, k)-connected Lemma 8 Let G be an n-vertex graph. If G is (5k -2)-connected and σ 2 (G) ≥ n + k -2 with k ≥ 2, then G is (2, k)-connected.
For the purpose of proof, let the orientation of P i be from x to u i for 1 ≤ i ≤ k and the orientation of Q j be from y to u i for 2 ≤ j ≤ k.

We denote P i = P i [x, u i ] and 4.1). Note that P ′ i and Q ′ j may be empty for

P ′ i = P i \ {x, u i } = P ′ i (x, u i ) for 1 ≤ i ≤ k. Let Q j = Q j [y, u j ], Q ′ j = Q j \ {y, u j } = Q ′ j (y, u j ) for 2 ≤ j ≤ k, and R = G -F (see Figure
1 ≤ i ≤ k and 2 ≤ j ≤ k. Claim 4.2.1 For 2 ≤ i ≤ k, |N G (u 1 ) ∩ V (Q ′ i )| ≤ 1 and |N G (y) ∩ (V (Q ′ i ) ∪ {u i })| = 1. Proof. It is clear that |N G (y) ∩ (V (Q ′ i ) ∪ {u i })| = 1 for 2 ≤ i ≤ k by assumption (I).
Toward a contradiction, suppose that there exists an integer i for

2 ≤ i ≤ k such that |N G (u 1 ) ∩ Q ′ i | ≥ 2. Without loss of generality, i = 2. Let v 1 and v 2 be the neighbours of u 1 in Q ′ 2 . The orientation of Q ′ 2 [v 1 , v 2 ]

This contradicts assumption (I). So |N

Q ′ i (u 1 )| ≤ 1 for 2 ≤ i ≤ k.

Claim 4.2.2

There exists an integer i for 2

≤ i ≤ k such that |Q ′ i | ≥ 2.
Proof. Suppose that |Q ′ i | ≤ 1 for each 2 ≤ i ≤ k. Let G ′ be a graph with order n ′ obtained by removing x and all vertices of Q i except y

for 2 ≤ i ≤ k from G. Hence we have n ′ = n -k -k i=2 |Q ′ i | and σ 2 (G ′ ) ≥ σ 2 (G) -2(k + k i=2 |Q ′ i |) ≥ n ′ -k -1.
It is easy to see that there exist at most k -1 vertices not dominated by u 1 and y. G ′ is still connected after deleting these vertices. So we obtain a path P in G ′ from u 1 to y such that |P | ≤ 4.

Let F be obtained from G by removing y, all internal vertices of P , and all vertices of Q ′ i for 2 ≤ i ≤ k. F is (4k -4)-connected. Hence we have an (x, U )-fan in F . Then we obtain an (X, U )-connection consisting of this (x, U )-fan, P , and

∪ k i=2 V (Q ′ i ) where X = {x, y}. It is a contradiction.

Claim 4.2.3 There exists an integer

i for 1 ≤ i ≤ k such that |N P ′ i (u 1 ) ∩ N P ′ i (y)| ≥ 1. Furthermore, we have |P ′ i | = 1 and |N P ′ i (u 1 )∩N P ′ i (y)| = 1. Proof. Suppose that N P ′ i (u 1 ) ∩ N P ′ i (y) = ∅ for 1 ≤ i ≤ k. Then d P ′ i (u 1 ) + d P ′ i (y) ≤ |P ′ i | for 1 ≤ i ≤ k and d {x} (u 1 ) + d {x} (y) ≤ 2. Since N R (u 1 ) ∩ N R (y) = ∅, we have d R (u 1 ) + d R (y) ≤ |R|. By Claim 4.2.1, we have d Q ′ i ∪{u i } (u 1 ) + d Q ′ i ∪{u i } (y) ≤ |Q ′ i | + 2 for 2 ≤ i ≤ k. To be specific, d Q ′ i ∪{u i } (u 1 ) + d Q ′ i ∪{u i } (y) ≤ 3 ≤ |Q ′ i | + 1 when |Q ′ i | ≥ 2 for 2 ≤ i ≤ k. If 0 ≤ |Q ′ i | ≤ 1, then d Q ′ i ∪{u i } (u 1 ) + d Q ′ i ∪{u i } (y) ≤ |Q ′ i | + 2 for 2 ≤ i ≤ k. By Claim 4.2.
2, we assume that there exists an integer j such that

d Q ′ j ∪{u j } (u 1 ) + d Q ′ j ∪{u j } (y) ≤ |Q ′ i | + 1. Since u 1 and y are not adjacent and σ 2 (G) ≥ n + k -2, we have n+k-2 ≤ d(u 1 )+d(y) ≤ k i=1 |P ′ i |+ 2≤i≤k i̸ =j (|Q ′ i |+2)+(|Q ′ j |+1)+|R|+2 = n+k-3.
We deduce a contradiction. Now there exists an integer i for

1 ≤ i ≤ k such that |N P ′ i (u 1 ) ∩ N P ′ i (y)| ≥ 1. Let v be any vertex in N P ′ i (u 1 ) ∩ N P ′ i (y). If P ′ i \ {v} ̸ = ∅, then it contradicts assumption (I). So |P ′ i | = 1 and |N P ′ i (u 1 ) ∩ N P ′ i (y)| = 1. Claim 4.2.4 For 1 ≤ i ≤ k, d P ′ i (u 1 ) + d P ′ i (y) ≤ |P ′ i | + 1. Proof. Obviously, d P ′ i (u 1 ) + d P ′ i (y) ≤ |P ′ i | when N P ′ i (u 1 ) ∩ N P ′ i (y) = ∅ for 1 ≤ i ≤ k. If there exists an integer i such that N P ′ i (u 1 ) ∩ N P ′ i (y) ̸ = ∅ for 1 ≤ i ≤ k, then |N P ′ i (u 1 ) ∩ N P ′ i (y)| = 1 by Claim 4.2.3. So d P ′ i (u 1 ) + d P ′ i (y) ≤ |P ′ i | + 1 for 1 ≤ i ≤ k.
Without loss of generality, we assume that v ∈ N P ′ 2 (u 1 )∩N P ′ 2 (y) and

P ′ 2 = {v} by Claim 4.2.3. For 2 ≤ i ≤ k, if |Q ′ i | = 0, then d Q ′ i ∪{u i } (u 1 ) + d Q ′ i ∪{u i } (y) ≤ 2. By the same argument as above, d Q ′ i ∪{u i } (u 1 ) + d Q ′ i ∪{u i } (y) ≤ 3 for 2 ≤ i ≤ k when |Q ′ i | ≥ 1. Since N R (u 1 ) ∩ N R (y) = ∅, we have d R (u 1 ) + d R (y) ≤ |R|. By Claim 4.2.4, we have d P ′ 1 ∪{x} (u 1 ) + d P ′ 1 ∪{x} (y) ≤ |P ′ 1 ∪ {x}| + 1 and d P ′ i (u 1 ) + d P ′ i (y) ≤ |P ′ i | + 1 for 2 ≤ i ≤ k. So n + k -2 ≤ d(u 1 ) + d(y) ≤ k i=2 (|P ′ i | + 1) + |P ′ 1 ∪ {x}| + 1 + 3(k -1) + |R|.
≤ i ≤ m -1. Note that V (S) = V (T ) and {r 1 , r 2 , u 1 } ⊆ V (T 1 ). Let v be any vertex of V (H). It is easy to see that d R (w) + d R (v) ≤ |R| -1. (4.3)
By the choices of r 1 and r 2 , we have wv / ∈ E(G). So

d T 1 [w,r 2 ] (w) + d T 1 [w,r 2 ] (v) ≤ |T 1 [w, r 2 ]|. (4.4) Since w is a non-insertable vertex of P 1 [r 1 , r 2 ], for 2 ≤ i ≤ k we have d T i \{x,y} (w) ≤        |T i \ {x, y}| + 1 2 , if T i \ {x, y} is odd, (4.5a
)

|T i \ {x, y}| 2 , otherwise .
(4.5b)

By the maximality of S, the neighbours of v in S are not adjacent. For

2 ≤ i ≤ k, we know that d T i \{x,y} (v) ≤ |T i \{x,y}|+1 2
. So we have

d T i \{x,y} (w) + d T i \{x,y} (v) ≤ |T i \ {x, y}| + 1. (4.6)
We now prove the following claim in order to obtain the degree sum of w and

v in T 1 [x,
d T 2 \{x,y} (v) ≤      |T 2 \{x,y}|-1 2 , if T 2 \ {x, y} is odd, |T 2 \{x,y}|-2 2
, otherwise, and so

d T 2 \{x,y} (w) + d T 2 \{x,y} (v) ≤      |T 2 \ {x, y}|, if T 2 \ {x, y} is odd, |T 2 \ {x, y}| -1, otherwise. (4.7) Note that (N G (w) ∩ V (T 1 [x, r 1 ])) ∩ (N G (v) ∩ V (T 1 [x, r 1 ])) + = ∅. Otherwise, let a = N G (v) ∩ V (T 1 [x, r 1 ]) and T ′ 1 = T 1 -aa + + wa + + aHr 1 . So T ′ = T 2 ∪T ′
1 is the union of k internally-disjoint paths connecting x to y such that u 2 ∈ T 2 -{x, y} and u 1 ∈ T ′ 1 with the order at least |V (S)|+1, this contradicts the maximality of S. By Lemma 7, we have

d T 1 [x,r 1 ] (w) + d T 1 [x,r 1 ] (v) ≤ |T 1 [x, r 1 ]| + 1, (

. The proof of Theorem 59

The proof of Theorem 59 is same as Theorem 58 mainly except the constraint of connectivity and degree sum. So we prove some claims without connectivity in this part.

Lemma 9

Let G be a graph with order n ≥ 4. For any two integers k 1 ≥ 2 and k 2 ≥ 2, if σ 2 (G)

≥ n + k 1 k 2 -2, then G is (k 1 , k 2 )-connected.
Proof. Suppose to the contrary that G is not (k 1 , k 2 )-connected, but for any e ∈ E(G), the graph G + e is (k 1 , k 2 )-connected where G is the complement of G.

Let X = {x 1 , x 2 , . . . , x k 1 } be a subset of V (G) and U = {u 1 , u 2 , . . . , u k 2 } be a subset of V (G) \ X. There exist k 1 k 2 -1 internally-disjoint paths connecting X to U . Without loss of generality, we denote these k 1 k 2 -1 internally-disjoint paths (∪ 1≤i≤k 1 -1,1≤j≤k 2 S i,j )∪ (∪ k 2 j=2 S k 1 ,j ). Let S i,j be the path connecting x i to u i for 1 ≤ i ≤ k 1 -1 and 1 ≤ j ≤ k 2 , and S k 1 ,j be the path connecting x k 1 to u j for 2 ≤ j ≤ k 2 .

Let F be a subgraph of G consists of all these k 1 k 2 -1 paths. Assume that the order of F is minimum, denoted by assumption (II).

For the purpose of proof, let the orientation of S i,j be from x i to u j for 1 ≤ i ≤ k 1 -1 and 1 ≤ j ≤ k 2 , and S k 1 ,j be from x k 1 to u j for 2 ≤ j ≤ k 2 . We denote S i,j = S i,j [x i , u j ] and S ′ i,j = S i,j \ {x i , u j } = S ′ i,j (x i , u j ) for 1 ≤ i ≤ k 1 -1 and 1 ≤ j ≤ k 2 . Let S k 1 ,j = S k 1 ,j [x k 1 , u j ] and S ′ k 1 ,j = S k 1 ,j \{x k 1 , u j } = S ′ k 1 ,j (x k 1 , u j ) for 2 ≤ j ≤ k 2 , and R = G-F (see Figure 4.4). Note that S ′ i,j and S ′ k 1 ,2 , S ′ k 1 ,3 , . . . , S ′ k 1 ,k 2 may be empty

for 1 ≤ i ≤ k 1 -1 and 1 ≤ j ≤ k 2 .
We obtain Claim 4.

Claim 4.3.1

There are two integers i and j for 1 ≤ i ≤ k 1 -1 and 1 ≤ j ≤ k 2 such that |N S ′ i,j (x k 1 ) ∩ N S ′ i,j (u 1 )| ≥ 1. Furthermore, |N S ′ i,j (x k 1 ) ∩ N S ′ i,j (u 1 )| = 1. Proof. Suppose that N S ′ i,j (x k 1 ) ∩ N S ′ i,j (u 1 ) = ∅ for 1 ≤ i ≤ k 1 -1 and 1 ≤ j ≤ k 2 . Then d S ′ i,j (u 1 ) + d S ′ i,j (x k 1 ) ≤ |S ′ i,j | for 1 ≤ i ≤ k 1 -1 and 1 ≤ j ≤ k 2 , and = n + k 1 + k 2 -4.

d {x i } (u 1 ) + d {x i } (x k 1 ) ≤ 2. Since N R (u 1 ) ∩ N R (x k 1 ) = ∅,
We deduce a contradiction, since k 1 (k 2 -1) > k 2 -2 when k 1 ≥ 2 and k 2 ≥ 2. Now there are two integers i and j for 1 ≤ i ≤ k 1 -1 and (d S ′ k 2 ,j ∪{u j } (u 1 ) + d S ′ k 2 ,j ∪{u j } (x k 2 ))

1 ≤ j ≤ k 2 such
+ k 1 -1 i=1 (d S ′ i,1 ∪{x i } (u 1 ) + d S ′ i,1 ∪{x i } (x k 2 )) + d R (u 1 ) + d R (x k 2 ) ≤ k 1 -1 i=1 k 2 j=2 (|S ′ i,j | + 1) + k 2 j=2 (|S ′ k 1 ,j | + 2) + k 1 -1 i=1 (|S ′ i,1 | + 2) + |R| = k 1 -1 i=1 k 2 j=2 |S ′ i,j | + (k 1 -1)(k 2 -1) + k 2 j=2 |S ′ k 1 ,j | + 2(k 2 -1) + k 1 -1 i=1 |S ′ i,1 | + 2(k 1 -1) + |R| = n + k 1 k 2 -3,
this is a contradiction. So we complete the proof of Lemma 9.

Let G be a graph satisfying the conditions of Theorem 59. For any k 1 -subset X = {x 1 , x 2 , . . . , x k 1 } of V (G), let U = {u 1 , u 2 , . . . , u k 2 } be a k 2 -subset of V (G) \ X. By Lemma 9, it follows that there exist k 1 k 2 internally-disjoint paths S i,j connecting x i to u j for 1 ≤ i ≤ k 1 and 1 ≤ j ≤ k 2 . Let the orientation of S i,j be from x i to u j for 1 ≤ i ≤ k 1 and 1 ≤ j ≤ k 2 . We denote S i,j = S i,j [x i , u j ],

S ′ i,j = S i,j \ {x i , u j } = S ′ i,j (x i , u j ) for 1 ≤ i ≤ k 1 and 1 ≤ j ≤ k 2 . Let S = ∪ 1≤i≤k 1 ,1≤j≤k 2 S i,j be the union of these k 1 k 2 internally-disjoint paths such that |V (S)| is maximum, and R = G -S. Proof. Suppose that there is no segment in S i,j for 1 ≤ i ≤ k 1 and 1 ≤ j ≤ k 2 . Let z be any vertex of V (H). We consider the following cases.

Case 1: N G (V (H)) ∩ X ̸ = ∅. Without loss of generality, we suppose that x 1 ∈ N G (V (H)). Let x + 1,1 be a successor of x 1 in S 1,1 . By the maximality of S, x + 1,1 and z are not adjacent. It is clear that there exist two integers i and j with 2 ≤ i ≤ k 1 and 1 ≤ j ≤ k 2 such that N G (V (H)) ∩ (V (S ′ i,j ) ∪ {x i }) ̸ = ∅. Otherwise, we can obtain the contradiction obviously by calculating the sum degree of x + 1,1 and z. Without loss of generality, we assume that N G (V (H)) ∩ (V (S ′ k 1 ,1 ) ∪ {x k 1 }) ̸ = ∅. For any vertex w ∈ N G (V (H)) ∩ (V (S ′ k 1 ,1 ) ∪ {x k 1 }), let w -be a predecessor of w in S k 1 ,1 . We have x + 1,1 w -/ ∈ E(G). If x + 1,1 w -∈ E(G), then it contradicts the maximality of S. So we obtain

d S 1,1 ∪S k 1 ,1 (z) + d S 1,1 ∪S k 1 ,1 (x + 1,1 ) ≤      |S 1,1 ∪ S k 1 ,1 | + 1, if y ∈ N G (V (H)), |S 1,1 ∪ S k 1 ,1 |, otherwise.
For 2 ≤ j ≤ k 2 , we have

d S ′ 1,j ∪S ′ k 1 ,j ∪{u j } (z) + d S ′ 1,j ∪S ′ k 1 ,j ∪{u j } (x + 1,1 ) ≤      |S ′ 1,j ∪ S ′ k 1 ,j ∪ {u j }|, if y ∈ N G (V (H)),
|S ′ 1,j ∪ S ′ k 1 ,j ∪ {u j }| + 1, otherwise.

For 2 ≤ i ≤ k 1 -1 and 1 ≤ j ≤ k 2 , we obtain

d S ′ i,j ∪{x i } (z) + d S ′ i,j ∪{x i } (x + 1,1 ) ≤ k 1 -1 i=2 k 2 j=1 |S ′ i,j ∪ {x i }| + 1.
By the maximality of S, we have d R (x

+ d R (x + 1,1 ) + d R (z) ≤ |S 1,1 ∪ S k 1 ,1 | + 1 + k 2 j=2 (|S ′ 1,j ∪ S ′ k 1 ,j ∪ {u j }| + 1) + k 1 -1 i=2 k 2 j=1 |S ′ i,j ∪ {x i }| + k 2 (k 1 -2) + |R| -1 = n + 1 + (k 2 -1) + k 1 k 2 -2k 2 -1 = n + k 1 k 2 -k 2 -1,
this is a contradiction.

Case 2: N G (V (H)) ∩ X = ∅.

For 1 ≤ i ≤ k 1 and 1 ≤ j ≤ k 2 , we have |N G (V (H)) ∩ (V (S ′ i,j ) ∪ {u j })| ≤ 1. Without loss of generality, we suppose v ∈ (V (S ′ 1,1 )∪{u 1 })∩ N G (V (H)). Let v -be a predecessor of v in S 1,1 . Note that v -and z are not adjacent. By the maximality of S, we have

N G (v -) ∩ (N G (z) ∩ (V (S ′ k 1 ,1 ) ∪ {x k 1 })) + = ∅. So d S 1,1 ∪S k 1 ,1 (v -) + d S 1,1 ∪S k 1 ,1 (z) ≤ |S 1,1 ∪ S k 1 ,1 | by Lemma 7. When N G (V (H)) ∩ V (S ′ 1,j ) ̸ = ∅ for 2 ≤ j ≤ k 2 .
Let w be any vertex of N G (V (H)) ∩ V (S ′ 1,j ) and w + be a successor of w in S ′ 1,j .

By the maximality of S, v -w + / ∈ E(G). For 2 ≤ j ≤ k 2 , we obtain

d S ′ 1,j (v -) + d S ′ 1,j (z) ≤      |S ′ 1,j | + 1, if w + = u i , |S ′ 1,j |, otherwise.
Since |N G (V (H)) ∩ (V (S ′ k 1 ,j ) ∪ {u j })| ≤ 1, we have

d S ′ k 1 ,j ∪{u j } (v -) + d S ′ k 1 ,j ∪{u j } (z) ≤      |S ′ k 1 ,j | + 1, if w + = u i , |S ′ k 1 ,j ∪ {u i }| + 1, otherwise. 100 So d S ′ 1,j ∪S ′ k 1 ,j ∪{u j } (v -) + d S ′ 1,j ∪S ′ k 1 ,j ∪{u j } (z) ≤ |S ′ 1,j ∪ S ′ k 1 ,j ∪ {u j }| + 1 for 2 ≤ j ≤ k 2 .
If N G (V (H)) ∩ V (S ′ 1,j ) = ∅ for 2 ≤ j ≤ k 2 , then d S ′ 1,j ∪S ′ k 1 ,j ∪{u j } (v -) + d S ′ 1,j ∪S ′ k 1 ,j ∪{u j } (z) ≤ |S ′ 1,j ∪ S ′ k 1 ,j ∪ {u j }| + 1. Hence for 2 ≤ j ≤ k 2 , we have

d S ′ 1,j ∪S ′ k 1 ,j ∪{u j } (v -) + d S ′ 1,j ∪S ′ k 1 ,j ∪{u j } (z) ≤ |S ′ 1,j ∪ S ′ k 1 ,j ∪ {u j }| + 1.
For 2 ≤ i ≤ k 1 -1 and 1 ≤ j ≤ k 2 , we have d S ′ i,j ∪{x i } (v -) + d S ′ i,j ∪{x i } (z) ≤ |S ′ i,j ∪ {x i }| + 1. By the maximality of S, d R (v

-) + d R (z) ≤ |R| -1. So n + k 1 k 2 -2 ≤ d(v -) + d(z) = d S 1,1 ∪S k 1 ,1 (v -) + d S 1,1 ∪S k 1 ,1 (z) + k 2 j=2 (d S ′ 1,j ∪S ′ k 1 ,j ∪{u j } (v -) + d S ′ 1,j ∪S ′ k 1 ,j ∪{u j } (z)) + k 1 -1 i=2 k 2 j=1 (d S ′ i,j ∪{x i } (v -) + d S ′ i,j ∪{x i } (z)) + d R (v -) + d R (z) ≤ |S 1,1 ∪ S k 1 ,1 | + k 2 j=2
(|S ′ 1,j ∪ S ′ k 1 ,j ∪ {u j }| + 1) +

k 1 -1 i=2 k 2 j=1
(|S ′ i,j ∪ {x i }| + 1)

+ |R| -1 = n + k 1 k 2 -k 2 -2.
It is a contradiction.

By Claim 4.3.3 and Claim 4.3.4, without loss of generality, we assume that

r 1 , r 2 ∈ N G (V (H)) ∩ V (S 1,1
) such that there is no vertex of S 1,1 [r + 1 , r - 2 ] which has a neighbour in H, and w is a non-insertable vertex of S 1,1 [r 1 , r 2 ] such that there is no non-insertable vertex of S 1,1 [r 1 , w -]. Clearly, S 1,1 [r 1 , r 2 ] is a segment of S. Let S 1,1 [r 1 , w] = y 0 y 1 . . . y m where y 0 = r 1 and y m = w. We denote S 1,1,k 1 = S 1,1 ∪ S k 1 ,u 1 and the orientation of S 1,1,k 1 is from x 1 to x k 1 . For any vertex z ∈ N G (V (H)) ∩ V (S 1,1,k 1 ) \ {r 1 }, let z + be a successor of z in S 1,1,k 1 .

We obtain the following claim with the same argument of Claim 4.2.7.

Claim 4.3.5 y i is not adjacent to z + for 1 ≤ i ≤ m.

-Conclusions and prospects

We first describe some open questions related to our results in the thesis. Then we would like to mention the prospects of my research.

. Open problem

. Generalisation of Hamiltion-connectivity

In Chapter 4, we prove that every graph G with n vertices is

(2, k)-Hamilton-connected if G is (5k -4)-connected and σ 2 (G) ≥ n + k -2
where k ≥ 2. The connectivity of G is mainly used to prove the existence of the (2, k)-connection. We want to improve this result if we remove the connectivity condition.

Another direction is to study sufficient conditions of (k 1 , k 2 )-Hamilton connected graphs. We have given a sufficient condition of (2, k)-Hamilton connected graphs. We will continue to consider the case when k 1 ≥ 3.

. Fractional colourings on triangle-free graphs

In Chapter 3, we know that χ f (4, K 3 ) lies between 3.25 and 3.5. Although we have improved the bound of χ f (4, K 3 ) to 3.466, there is still room for improvement.

The same question for larger values of the maximum degree is still open.

In fact, we have done some work on further loosening of the constraints of degree-4 vertices. It is a well-known fact that, given any graph G, if H is the bipartite spanning subgraph of G induced by a maximum cut, then deg H (v) ≥ deg G (v)/2 for every vertex v ∈ V (G) (this actually holds even if H is induced by a maximal cut, up to moving any vertex from one part to the other). By using this method, we could improved 3.4663 to 3.456.

. Future research

. Proper conflict-free colourings

as ∆ → ∞.

. Odd colouring

A proper vertex-colouring of a graph G is said to be odd if for each non-isolated vertex there is a colour appearing an odd number of times on its neighbourhood.

It is introduced by Petruševski and Škrekovski [START_REF] Petruševski | Colorings with neighborhood parity condition[END_REF]. The odd chromatic number In the last couple of years, there has been some interest in determining the extremal value of χ o in various classes of graphs. Petruševski and Škrekovski [START_REF] Petruševski | Colorings with neighborhood parity condition[END_REF] showed that χ o (G) ≤ 9 for every planar graph G with a proof that relies on the discharging method. Furthermore, they conjectured that this bound may be reduced to 5. If true, this would be tight, since χ o (C 5 ) = 5.

Caro, Petruševski, and Škrekovski [START_REF] Caro | Remarks on odd colorings of graphs[END_REF] also studied various properties of the odd chromatic number of general graphs; in particular, they proved the following facts: every graph of maximum degree three has an odd 4-colouring; every graph, except for C 5 , of maximum degree ∆ has an odd 2∆-colouring. Moreover, they presented a conjecture for general graphs. Recently, Dai, Ouyang, and Pirot [START_REF] Dai | New bounds for odd colourings of graphs[END_REF] used the probabilistic method to prove that for every graph G with maximum degree ∆, χ o (G) ≤ ∆+O(ln ∆) as ∆ → ∞.

We also prove that χ o (G) ≤ ⌊3∆/2⌋+2 for every ∆. We will study this conjecture in the near future.

1. 1 A

 1 proper 3-colouring of the Petersen graph . . . . . . . . . . . . . 1.2 C 4 and two covers of it such that C 4 is (L, H 1 )-colourable but not (L, H 2 )-colourable. . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 The chromatic number and the fractional chromatic number of C 5 , the right figure is also a proper (5 : 2)-colouring of C 5 . . . . . . . 1.4 The two cubic triangle-free connected graphs with Hall ratio 14 5 . . 1.5 A graph certifying that χ f (4, K 3 ) ≥ 3.25. . . . . . . . . . . . . . 1.6 Hamilton's puzzle: the graph of the dodecahedron . . . . . . . . . 2.1 Two examples of the M L -cover of C 4 such that |L(u)| = 2 for any vertex u. Each thin rectangle represents {u} × L(u) for some vertex u. In fact, the cycle C 4 admits an M L -colouring for the left, but it does not for the right . . . . . . . . . . . . . . . . . . 2.2 The graph H 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 The graph G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 u and v are vertices lying on the outer cycle of G and the black lines, dotted lines, and doublet lines represent the edges in M L , M 1 L , M 2 L , respectively. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 u, v, and w are vertices lying on the outer cycle of G and the black lines, dotted lines, and doublet lines represent the edges in M L , M 1

  cover. The black vertices are in U 1 and U 2 . . . . . . . . . . . . . . . . . . . . . . .

vi 2 . 7 4 . 2 F

 2742 The left graph is a part of the (M L ∪ M 1 L ∪ M 2 L )-cover when the case that the degree of b j-1 in H[ L(v j-1 ) ∪ L(v j )] is one and the right one is the other case. The black vertices are in A j and the vertices surrounded by squares are in B j . . . . . . . . . . . . . . . 2.8 An example of choosing c 0 , d 0 , c m+1 , and d m+1 and adding the edges c 0 d m+1 and d 0 c m+1 for m = 3. . . . . . . . . . . . . . . . 2.9 The black vertices are in U i for each 1 ≤ i ≤ m and j max = 4 ̸ = m. 3.1 A graph certifying that χ f (4, K 3 ) ≥ 3.25. . . . . . . . . . . . . . 3.2 Dangerous graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 The patterns rooted in a degree-3 vertex that yield a minimal refined constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Two possible patterns rooted at v with N G [v] ∩ S 4 ̸ = ∅, and their related constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 A possible pattern rooted at v with N G [v] ∩ S 4 ̸ = ∅, and its related constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 The maximal counterexample of a (2, k)-Hamilton-connected graph. ′ with fewer vertices than F . . . . . . . . . . . . . . . . . . . . 4.3 P ab is a segment of S. P ab [w 1 , w h 1 ] is inserted by an edge a 1 b 1 . P ab [w h 1 +1 , w h 2 ] is inserted by an edge a 2 b 2 . . . . . . . . . . . . . 4.4 The maximal counterexample of a (k 1 , k 2 )-Hamilton-connected graph. vii Résumé La décomposition des graphes fait référence au processus de décomposer un graphe complexe en composantes plus simples et plus petites, souvent dans le but d'analyser ou de résoudre des problèmes liés au graphe. Il s'agit d'un outil important pour représenter la structure globale et les propriétés d'une manière plus détaillée. Il est aussi également utile pour résoudre des problèmes impliquant la recherche de structures spécifiques dans un graphe. Parmi les nombreuses applications possibles, nous pourrions mentionner les problèmes d'enracinement, un réseau où plusieurs paires source-destination doivent communiquer. Pour garantir la résilience de la communication en cas de défaillance d'un noeud le long d'un lien, nous devons maintenir des liens de communication entre plusieurs paires source-destination. L'objectif dans un graphe est de trouver des chemins internement disjoints entre ces paires, où chaque chemin devrait être unique et ne partager aucun noeud commun avec un autre chemin. Ainsi, si un chemin devient déconnecté dans une paire source-destination, nous pouvons trouver un nouveau chemin pour les relier. Il existe plusieurs types courants de techniques de décomposition de graphe largement utilisées en théorie des graphes et dans des domaines connexes, notamment la décomposition en arbres, la décomposition en blocs, la décomposition modulaire, la décomposition hiérarchique, etc. Cette thèse étudie deux types de décomposition de sommets d'un graphe : les colorations propres (décomposition en ensembles indépendants) et la Hamilton-connectivité (décomposition en chemins internement disjoints entre deux ensembles où les chemins couvrent tous les sommets du graphe).

  qui couvrent tous les sommets de G. Il est évident que la (1, k 2 )-Hamilton-connexité est équivalente à la k 2 -fan-connexité. Soit σ 2 (G) la valeur minimale de deg(u)+deg(v) sur toutes les paires {u, v} de sommets non adjacents dans G. Nous prouvons qu'un graphe G à n sommets est (2, k)-Hamilton-connexe si G est (5k-4)-connexeavec σ 2 (G) ≥ n + k -2 où k ≥ 2. Nous prouvons également que si σ 2 (G) ≥ n + k 1 k 2 -2 avec k 1 , k 2 ≥ 2, alors G est (k 1 , k 2 )-Hamilton-connexe. De plus, nous construisons deux graphes pour montrer que nos résultats sont optimaux. Nous concluons cette thèse dans le Chapitre 5 et présentons quelques perspectives.

Figure 1 . 1 :

 11 Figure 1.1: A proper 3-colouring of the Petersen graph

deg(v) ≤ 4 ,

 4 then every 5-colouring of G -v extends to a 5-colouring of G. If deg(v) = 5, then we find two non-adjacent neighbours x and y of v, and let G ′ be the graph obtained from G -v by identifying x and y to a new vertex w.

Figure 1 . 3 :

 13 Figure 1.3: The chromatic number and the fractional chromatic number of C 5 , the right figure is also a proper (5 : 2)-colouring of C 5 .

  in a stronger lower bound. The Hall ratio of G, denoted ρ(G), and defined by

  then any fractional colouring of G must have a weight of at least |W |, and hence we have

  g → ∞ of ρ(d, g). Note that if we fix d, then ρ(d, g) is a non-increasing function of g. In symbols, ρ(d, g) := sup{|V (G)|/α(G) : G is a graph with ∆(G) ≤ d and girth(G) ≥ g}, and ρ(d, ∞) = lim g→∞ ρ(d, g).

Figure 1 . 4 :Figure 1 . 5 :

 1415 Figure 1.4:The two cubic triangle-free connected graphs with Hall ratio14 5 .

  For triangle-free d-degenerate graphs, the chromatic number of such a graph can be as large as d + 1. Notably, the only known examples of graphs reaching this bound have a much smaller fractional chromatic number. As a result, Harris has put forth the following conjecture.

Figure 1 . 6 :

 16 Figure 1.6: Hamilton's puzzle: the graph of the dodecahedron

  Finding a good necessary and sufficient condition for a graph to have a Hamilton cycle (path) turns out to be impossible. Naturally, there has been much literature on graph theory studying sufficient conditions for hamiltonicity.Research on sufficient conditions for the existence of Hamilton cycles often involves conditions on the edge density, or equivalently, conditions related to the number of neighbouring vertices. If a graph G has k independent vertices with k ≥ 1, we define:

34 4 .

 4 The spanning connectivity of G, κ *

5 . 1 .

 51 Hamilton-connected graphs Motivated by spanning connectivity and k-fan connected graphs, we define (k 1 , k 2 )-Hamilton-connected graphs. Definition 11. A graph G is (k 1 , k 2 )-Hamilton-connected, if for any two disjoint vertex subsets X = {x 1 , x 2 , . . . , x k 1 } and U = {u 1 , u 2 , . . . , u k 2 }, there are k 1 k 2 internally-disjoint paths connecting x i to u j for 1 ≤ i ≤ k 1 and 1 ≤ j ≤ k 2 , which span the whole graph. Remark (1, k)-Hamilton-connectivity is equivalent to k-fan-connectivity. 2. Both (1, 1)-Hamilton-connectivity and (1, 2)-Hamilton-connectivity are equivalent to Hamilton-connectivity. 3. (k, k)-Hamilton-connectivity implies k-link. In 2022, Dai, Li, Ouyang, and Tian studied (2, k)-Hamilton-connected graphs.

[

  Corresponding paper: On (2,k)-Hamilton-connected graphs, Submited to Discrete Applied Math. in Aug. 2022, with Hao Li, Qiancheng Ouyang, and Zengxian Tian.]

1 .

 1 For each edge uv in E(G), let M L,uv be the union of µ G (uv) matchings between {u} × L(u) and {v} × L(v) where µ G (uv) is the multiplicity of uv in G. Note that if u and v are not connected by an edge in G, then µ G (uv) = 0 and M L,uv is an empty set. With abuse of notation, we sometimes regard M L,uv as a bipartite graph between {u} × L(u) and {v} × L(v) of maximum degree at most µ G (uv). Let M L = {M L,uv : uv ∈ E(G)}, which is called a matching assignment over L. Then a graph H is said to be the M L -cover of G if it satisfies the following conditions:

(

  iii) For every two vertices u and v in G, {u} × L(u) and {v} × L(v) induce in H the graph obtained from M L,uv by adding those edges defined in (ii). (See Figure 2.1 for an example)2. An M L -colouring of G is an independent set I in the M L -cover with |I| = |G|. G is said to be M L -colourable if it admits an M L -colouring.

Figure 2 . 1 :

 21 Figure 2.1: Two examples of the M L -cover of C 4 such that |L(u)| = 2 for any vertex u. Each thin rectangle represents {u} × L(u) for some vertex u. In fact, the cycle C 4 admits an M L -colouring for the left, but it does not for the right

Figure 2 .

 2 1 is the ladder of length 4. • A graph G is the Möbius ladder of length n if it is obtained from the P n 2K 2 with P n = v 1 . . . v n and V (K 2 ) = {a, b} by adding the edges (v 1 , a)(v n , b) and (v 1 , b)(v n , a). The right graph in Figure 2.1 is the Möbius ladder of length 4.

Figure 2 . 3 :

 23 Figure 2.3: The graph G

Figure 2 . 4 : 1 L , M 2 L

 2412 Figure 2.4: u and v are vertices lying on the outer cycle of G and the black lines, dotted lines, and doublet lines represent the edges in M L , M 1 L , M 2 L , respectively.

Figure 2 .

 2 Figure 2.4 shows an example. The left matching assignments in Figure 2.4

Figure 2 .

 2 Figure 2.5 shows an example. We can regard ML ∪M 1 L ∪M 2 L as a matching assignment M ′ L of G m over L. Then G m admits an M ′ L -colouring if and only if G admits an (M L ∪ M 1 L ∪ M 2 L )-colouring.

Figure 2 . 5 :

 25 Figure 2.5: u, v, and w are vertices lying on the outer cycle of G and the black lines, dotted lines, and doublet lines represent the edges in M L , M 1 L , M 2

  then we do not need to consider conditions (I)-(IV) in Theorem 54. Hence we have only to prove Theorem 54.

  fat ladder nor a t-fat Möbius ladder by assumption (I) of Theorem 54. Suppose that there is no vertex u ∈ V (G) with |L(u)| ≥ 5. The number of matching assignments in the (M L ∪ M 1 L ∪ M 2 L )-cover is at most two by assumption (III) of Theorem 54. Recall that for an edge uv ∈ E(C), the number of matching assignments between L(u) and L(v) in (M L ∪ M 1 L ∪ M 2 L )-cover corresponds to the multiplicity of uv in G m . For a vertex v ∈ V (G) with |L(v)| = 4 and a vertex w ∈ L(v), the number of edges in the (M L ∪ M 1 L ∪ M 2 L )-cover incident with w is at most four since the number of matching assignments in the (M L ∪ M 1 L ∪ M 2 L )-cover is at most two. Moreover, for a vertex v ∈ V (G) with |L(v)| = 3 and a vertex w ∈ L(v), the number of edges in (M L ∪ M 1 L ∪ M 2 L )-cover incident with w is at most three by assumption (IV). Hence for each vertex v ∈ V (G) and each vertex w ∈ L(v), the number of edges in

  by the construction above. Since the number of vertices in L(u) adjacent to one of I ′ ∩ ( L(u 1 ) ∪ L(u 2 )) is at most four and |L(u)| ≥ 5, there is a vertex v ∈ L(u) not adjacent to

  so |L(v j )| ≥ 4 by assumption (IV) of the theorem. Then |A j | ≥ 3 and |B j | ≥ 2. By assumption (I) of the theorem, we can take the desired two vertices a j ∈ A j and b j ∈ B j (see the right side of Figure 2.7). Now we complete the proof of Claim 2.3.1.

  Figure 2.7: The left graph is a part of the (M L ∪ M 1 L ∪ M 2 L )-cover when the case that the degree of b j-1 in H[ L(v j-1 ) ∪ L(v j )] is one and the right one is the other case. The black vertices are in A j and the vertices surrounded by squares are in B j .

1 L

 1 and d m+1 ∈ L(v m+1 ) ∩ N H (b m ) (possibly some of c 0 , d 0 , c m+1 , and d m+1 do not exist). We add the edges c 0 d m+1 and d 0 c m+1 to M 1 L ′ if they are not in M ′ (see Figure 2.8). Since the graph induced by the edges connecting L(v 0 ) and L(v m+1 ) in the

Figure 2 . 8 :

 28 Figure 2.8: An example of choosing c 0 , d 0 , c m+1 , and d m+1 and adding the edges c 0 d m+1 and d 0 c m+1 for m = 3.

Figure 2 . 9 :

 29 Figure 2.9: The black vertices are in U i for each 1 ≤ i ≤ m and j max = 4 ̸ = m.

(

  ii) j max = m.Proof. (i) Suppose that the vertex inI ′ ∩ L(v 0 ) is degree at most one in H. Note that I ′ ∩ L(v m+1) is a set that contains a single vertex. By Claim 2.3.3, there exists a good pair {a 1 , b 1 } of two vertices in L(v 1 ) such that a 1 and b 1 are not adjacent to the vertex in I ′ ∩ L(v 0 ). By Claim 2.3.1, there exist two vertex sets A = {a 1 , a 2 , . . . , a m } and B = {b 1 , b 2 , . . . , b m } satisfying the conditions (i)-(iii) of Claim 2.3.1. Since the degree of the vertex in I ′ ∩ L(v m+1 ) is at most one, one of a m and b m , say a m , is not adjacent to the vertex in

  respectively, by deleting the edges incident with the vertices in U 0 . Note that 1 ≤ |U 0 | ≤ 2 by assumption (I) of Theorem 54, so 2 ≤ |L ′′ (v 0 )| ≤ 3, |L ′′ (v m+1 )| ≥ deg G (v m+1 ) ≥ 3, and the graph induced by the edges connecting L ′′ (v 0 ) and L ′′ (v m+1 ) is a matching.

  be isomorphic to a ladder of odd length or a Möbius ladder of even length by assumption (I) of Theorem 54.

  there are at least three vertices in L(v 1 ) not adjacent to the vertex in I ′ ∩ L(v 0 ) and so we can take a desired good pair by assumption (I) of Theorem 54. Hence we may assume that |L(v 1 )| = 3. By Claim 2.3.5 and assumption (IV) of Theorem 54, H[ L(v 1 ) ∪ L(v 2 )] is a matching. Hence the pair of two vertices not adjacent to the vertex in I ′ ∩ L(v 0 ) is a desired good pair. By Claim 2.3.1, there exist vertex sets A = {a 1 , a 2 , . . . , a m } and B = {b 1 , b 2 , . . . , b m } satisfying conditions (i)-(iii) of Claim 2.3.1. Suppose that |L(v m )| = 3. Then by assumption (III) of Theorem 54, there is a vertex u m in L(v m ) not adjacent to the vertex in I ′ ∩ L(v m+1 ). By Claim 2.3.5 and assumption (IV) of Theorem 54, H[ L(v m-1 ) ∪ L(v m )] is a matching and so one of a m-1 and b

  then there are at most two vertices in L(v m ) adjacent to the vertex in I ′ ∩ L(v m+1 ) by assumption (III) of Theorem 54. If |L(v m )| ≥ 5, then there are at most three vertices in L(v m ) adjacent to the vertex in I ′ ∩ L(v m+1 ). In both cases, there are at least two vertices in L(v m ) not adjacent to the vertex in I ′ ∩ L(v m+1 ) and so there is a vertex w m in L(v m ) not adjacent to the vertices in

  Figure 3.1: A graph certifying that χ f (4, K 3 ) ≥ 3.25.

Claim 3 . 2 . 1

 321 If the solution of the linear program LP * φ (G) is at most ∆(G) + 1, then it matches the solution of LP φ (G).

  for every I ∈ I , where Z I (λ) = J∈I λ |J| is the partition function associated with I.

Figure 3 . 2 :

 32 Figure 3.2: Dangerous graphs

  .2). A vertex is dangerous if it has degree 2 in a dangerous graph. A vertex v ∈ V (G) is special if it belongs to a dangerous subgraph of G, and has degree 2 in G. Given a subset B of the dangerous vertices of G, we say that a vertex v of degree 2 in a dangerous subgraph H of G is nailed by B if either v belongs to B, or v is not special (i.e has degree 3 in G). A nail B of G is a subset of the dangerous vertices of G such that for every dangerous subgraph H of G, at least 2 vertices of degree 2 in H are nailed by B.

  the random event that I 0 \ N [v] = J. By the Spatial Markov Property, given a vertex v ∈ V (G), if we condition on the event E J , then I 0 ∩ N [v] follows the hard-core distribution at fugacity λ on the independent sets of a star K 1,d centred in v, where d = |N (v) \ N (J)|. A classical analysis of the hard-core model yields that P [v ∈ I 0 | E J ] = λ λ + (1 + λ) d , and

Figure 3 . 3 :

 33 Figure 3.3: The patterns rooted in a degree-3 vertex that yield a minimal refined constraint

Figure 3 . 4 :

 34 Figure 3.4: Two possible patterns rooted at v with N G [v] ∩ S 4 ̸ = ∅, and their related constraints

Figure 3 . 5 :

 35 Figure 3.5: A possible pattern rooted at v with N G [v] ∩ S 4 ̸ = ∅, and its related constraints

Figure 4 . 1 :Figure 4 . 2 :

 4142 Figure 4.1: The maximal counterexample of a (2, k)-Hamilton-connected graph.

Figure 4 .

 4 Figure 4.3: P ab is a segment of S. P ab [w 1 , w h 1 ] is inserted by an edge a 1 b 1 .

(4. 9 ) 2 ,d T 2

 922 Since now σ 2 (G) ≥ n, by (4.3), (4.4), (4.7), (4.8), and (4.9), we haven ≤ d(w) + d(v) = d T 1 [x,r 1 ] (w) + d T 1 [x,r 1 ] (v) + d T 1 [w,r 2 ] (w) + d T 1 [w,r 2 ] (v) + d T 1 [r + 2 ,y] (w) + d T 1 [r + 2 ,y] (v) + d T 2 \{x,y} (w) + d T 2 \{x,y} (v) + d R (w) + d R (v) ≤ n -1.This is a contradiction.If vy /∈ E(G), then we haved T 2 \{x,y} (v) ≤ if T 2 \ {x, y} is odd, \{x,y} (w) + d T 2 \{x,y} (v) ≤ |T 2 \ {x, y}|.

For 2 ≤ j ≤ k 2 ,

 22 3 and Claim 4.3.2 by the same arguments as with Claim 4.2.1 and Claim 4.2.4. |NG (u 1 ) ∩ V (S ′ k 1 ,j )| ≤ 1 and |N G (x k 1 ) ∩ (V (S ′ k 1 ,j ) ∪ {u j })| = 1.

Figure 4 . 4 :

 44 Figure 4.4: The maximal counterexample of a (k 1 , k 2 )-Hamilton-connected graph.

k 1

 1 we have d R (u 1 ) + d R (x k 1 ) ≤ |R|. By Claim 4.3, we have d S ′ k 1 ,j ∪{u j } (u 1 ) + d S ′ k 1 ,j ∪{u j } (x k 1 ) ≤ |S ′ k 1 ,j | + 2 for 2 ≤ j ≤ k 2 . Since u 1 and x k 1 are not adjacent and σ 2 (G) ≥ n + k 1 k 2 -2, we have n + k 1 k 2 -2 ≤ d(u 1 ) + d(x k 1 ) ,j | + 2) + |R| + 2(k 1 -1)

If

  |V (S)| = |V (G)|, then Theorem 59 is proved. So let H be a component of R. We obtain the following claim by the same argument with Claim 4.2.5.

Claim 4 . 3 . 3

 433 Every segment of S contains a non-insertable vertex.

Claim 4 . 3 . 4

 434 There exists a segment in S i,j for 1 ≤ i ≤ k 1 and 1 ≤ j ≤ k 2 .

  of a graph G, denoted by χ o (G), is the minimum k ∈ N such that there exists an odd colouring σ : V (G) → [k]. Since odd colourings are a weakening of pcf colourings, it always holds that χ o (G) ≤ χ pcf (G) for every graph G.

Conjecture 8 (

 8 Caro, Petruševski, Škrekovski [22, Conjecture 5.5]) If G is a connected graph of maximum degree ∆ ≥ 3, then χ o (G) ≤ ∆ + 1.

Corollary 2

 2 For k ≥ 2, a graph is k-connected if and only if it has at least two vertices and any two vertices can be joined by k independent paths. Also, for k ≥ 2, a graph is k-edge-connected if and only if it has at least two vertices and any two vertices can be joined by k edge-disjoint paths.

	1.2 . Colourings
	The Four Colour Theorem is one of the most captivating and challenging
	episodes in the history of mathematics. It spans over a century and involves the
	contributions of numerous mathematicians and computer scientists. The origins
	of the Four Colour Theorem can be traced back to 1852 when Francis Guthrie, a
	mathematics student, posed the conjecture to his brother Frederick Guthrie. He
	noticed that he could colour the counties of England on a map using only four
	colours in such a way that no two adjacent counties shared the same colour. This
	observation led to the formulation of the Four Colour Conjecture. Many tried
	to prove or disprove this conjecture, but it remained unsolved for decades. In
	1879, Alfred Kempe presented a proof, but it turned out to be flawed, as Percy
	Heawood pointed out in 1890. It took more than a century before a valid proof was
	established by Kenneth Appel and Wolfgang Haken from the University of Illinois,
	using the discharge method in 1976. Their groundbreaking proof relied heavily

A path is called a Hamiltonian path if it visits each vertex of G exactly once. If for every pair of vertices in G there is a Hamiltonian path between the two vertices, we say that G is Hamilton-connected.

A cycle is called a Hamiltonian cycle if it visits each vertex of G exactly once.

If G has a Hamiltonian cycle, then G is a Hamiltonian.

  Figure 1.2: C 4 and two covers of it such that C 4 is (L, H 1 )-colourable but not (L, H 2 )-colourable.

	between L(u) and L(v) in H.
	Definition 4. Suppose G is a graph and (L, H) is a cover of G. An
	(L, H)-colouring of G is an independent set I ⊆ V (H) of size |V (G)|. In
	this context, we refer to the vertices of H as the colours. G is said to be
	(L, H)-colourable if it admits an (L, H)-colouring.
	Definition 5. Let G be a graph and f : V (G) → Z ≥0 be an assignment
	of nonnegative integers to the vertices of
	Definition 3. Let G be a graph. A cover of G is a pair (L, H), where L is a list
	assignment of pairwise disjoint sets to the vertices of G and H is a graph with
	vertex set ∪ v∈V (G) L(v), satisfying the following conditions.
	1. For each v ∈ V (G), H[L(v)] is a complete graph.
	2. For each uv ∈ E(G), the edges between L(u) and L(v) form a matching
	(possibly empty).
	3. For each distinct u, v ∈ V (G) with uv / ∈ E(G), there are no edges

  We say that two covers (L, H) and (L ′ , H ′ ) are equivalent if one can be obtained from the other by a sequence of renaming. The following are some useful facts about equivalent covers. Let (L, H) and (L ′ , H ′ ) be equivalent covers for a graph G. Then G is (L, H)-colourable if and only if it is (L ′ , H ′ )-colourable. Then there exists a cover (L ′ , H ′ ), equivalent to (L, H), such that L ′ assigns the list [k] to each vertex.

	Fact 1 Fact 2 Let (L, H) be a cover for a graph G such that for each vertex v,
	|L(v)| = k. So we may assume that each vertex is assigned the list [k] when we study
	DP-colourings where every list has size k for some integer k. In fact, list colourings
	are a specific case of DP-colourings. Given a list L for a graph G, the vertex set
	of its cover H = H(G, L) is {(v, c)|v ∈ V (G) and c ∈ L(v)}, and two different
	vertices (v, c) and (v
	),	otherwise.

and for each e ∈ E(G) incident with v, and

H ′ [L(v)] is obtained from H[L(v)] by

replacing the vertex c 1 by c 2 . We say (L ′ , H ′ ) is obtained from (L, H) by renaming (at a vertex v). ′ , c ′ ) are adjacent in H if and only if either c = c ′ and

  findings indicate that the first bound of Hutchinson's results is not sufficient for DP-colourings. Moreover, we give a sharp bound on DP-colourings for all the 2-connected outerplanar graphs. This work is illustrated precisely in Chapter 2. We are interested in fractional colourings of triangle-free graphs of maximum degree at most d with a specific focus on the case d = 4.Given a graph H, we let χ f (d, H) be the supremum of the fractional chromatic numbers over all H-free graphs of maximum degree at most d. It has been settled by Dvořák, Sereni, and Volec [39] that χ f (3, K 3 ) = 14/5. For d ∈ [16] \ {3}, there is an upper bound χ f (d, K 3 ) ≤ d+3 2 , which follows from the fractional Reed bound, established by Molloy and Reed

[Corresponding paper: On DP-colourings of outerplanar graphs, Submited to Discrete Math. in Oct. 2022, with Jie Hu, Hao Li, and Shun-ichi Maezawa.]

(2)

2.3.1

  Claims 2.3.2, 2.3.3, 2.3.5, and 2.3.6). Let i be a fixed integer with 1 ≤ i ≤ m. For every good pair {a i , b i } of two vertices in L(v i ), there exist vertex sets A = {a i , a i+1 , . . . , a m } and B

	Claim

  where S 0 4 is the set of isolated vertices in G[S 4 ] (and hence each vertex in S + 4 has a neighbour in S 4 ). Let us construct a random dominating set X of H[S 4 ], so that H \ X is indeed subcubic. Let F be a spanning forest of H[S + 4 ], and c be a proper 2-colouring of F . We let X + be a random colour class of

	Claim 3.3.1 There exists a random set X ⊆ S 4 such that H \ X is
	deterministically subcubic, and P [v ∈ X] = 1/2 for every v ∈ S + 4 .
	Proof.

  Claim 3.3.2 For every vertex v ∈ V (H) of degree at most 3, the refined constraint e + φ ′ ,H (v) is looser than a convex combination of constraints from d≤3 E +

φ (d).

Table 3 .

 3 Theorem 59 Let G be an n-vertex graph. If σ 2

	=	0.4131956355890983 0.8171186900623122	,		0.3875949146727972 0.8623039624795835	,	0.3619941937564962 0.9792992570670792	,
		0.3235931123820447 0.9840353904365947	,	0.3363934728401952 0.9516504784774741	;
	E φ0 (3) =	0.29164468339150756 1.3313975884273366	,	0.2735750004056644 1.3841637731984464	,	0.2555053174198213 1.5641504645155335	,
		0.22840079294105667 1.4770428472298294	,		0.23743563443397822 1.4333115039516406	,	0.21936595144813514 1.5352254194759454	;
	E φ0 (4) =	0.12061460778924579 1.966740049953671	,	0.08933488585220072 2.178014577640148	.

1: The constraints of the final linear program, with λ := 0.51.

  we can not find k 1 k 2 internally-disjoint paths connecting each pair {x, u} where x ∈ X and u ∈ U .

The remainder of this chapter is organized as follows. In Section 4.2, we prove Theorem 58. The first part of this section is to prove G is (2, k)-connected. In the second part of it, we prove that G is (2, k)-Hamilton-connected. In section 4.3, we show Theorem 59. In Section 4.4, we present a polynomial-time algorithm to find a spanning (X, U )-connection given two disjoint vertex subsets X = {x, y} and U = {u 1 , u 2 , . . . , u k } with k ≥ 2 for any graph satisfying the hypotheses of Theorem 58.

  3: P ab is a segment of S. P ab [w 1 , w h 1 ] is inserted by an edge a 1 b 1 . P ab [w h 1 +1 , w h 2 ] is inserted by an edge a 2 b 2 . Every segment of S contains a non-insertable vertex.Proof. Suppose to the contrary that there exists a segment P w 1 ws = w 1 w 2 . . . w s not containing any non-insertable vertex. Let T be the resulting graph of S after using a segment insertion SI[P w 1 ws [w 2 , w s-1 ]].Then T ∪ w 1 Hw s is the set of k internally-disjoint paths connecting x to y such that u i ∈ S i \{x, y} for 1 ≤ i ≤ k with the order at least |V (S)|+1, which contradicts the maximality of S.for 2 ≤ i ≤ k, and T 1 is obtained by S 1 removing all y i for 1

is inserted by cd. If c and d do not exist, then we call the internal vertex w is a non-insertable vertex. Suppose that w 1 , w 2 , . . . , w s are insertable vertices of the segment P ab in order along P ab . Let h 1 := max {i : w i can be inserted by an edge which w 1 can be inserted by} and we suppose that w 1 and w h 1 can be inserted by an edge a 1 b 1 . Let h 2 := max {i : w i can be inserted by an edge which w h 1 +1 can be inserted by} and we suppose that w h 1 +1 and w h 2 can be inserted by an edge a 2 b 2 . Continuing in the same procedure, we have h t = s for some t ≥ 1. Then we insert P ab [w 1 , w h 1 ] between a 1 and b 1 , P ab [w h 1 +1 , w h 2 ] between a 2 and b 2 , . . . , P ab [w h t-1 +1 , w ht ] between a t and b t (see Figure

4

.3). We call such an operation a segment insertion of P ab [w 1 , w s ] and denote it by SI[P ab [w 1 , w s ]].

Claim 4.2.5

  that |N S ′ i,j (x k 1 ) ∩ N S ′ i,j (u 1 )| ≥ 1. Let v be any vertex in N S ′ i,j (x k 1 ) ∩ N S ′ i,j (u 1 ). If S ′ i,j \ {v} ̸ = ∅, then it contradicts Assumption (II). So |S ′ i,j | = 1 and |N S ′ i,j (x k 1 ) ∩ N S ′ i,j (u 1 )| = 1. For 1 ≤ i ≤ k 1 -1, 1 ≤ j ≤ k 2 , d S ′ i,j (u 1 ) + d S ′ i,j (x k 1 ) ≤ |S ′ i,j | + 1. is easy to see that d R (u 1 ) + d R (x k 1 ) ≤ |R|. By Claim 4.3, we have d S ′ k 1 ,j ∪{u j } (u 1 ) + d S ′ k 1 ,j ∪{u j } (x k 1 ) ≤ |S ′ k 1 ,j | + 2 for 2 ≤ j ≤ k 2 .We also have d S ′ i,1 ∪{x

	We now infer that
	n + k 1 k 2 -2 ≤ d(u 1 ) + d(x k 2 )
	k 1 -1	k 2	k 2
	=	(d S ′ i,j (u 1 ) + d S ′ i,j (x k 2 )) +
	i=1	j=2	j=2
	Claim 4.3.2 It 97

i } (u 1 ) + d S ′ i,1 ∪{x i } (x k 1 ) ≤ |S ′ i,1 | + 2 for 1 ≤ i ≤ k 1 -1.

  + 1,1 ) + d R (z) ≤ |R| -1. So n + k 1 k 2 -2 ≤ d(x + 1,1 ) + d(z) = d S 1,1 ∪S k 1 ,1 (z) + d S 1,1 ∪S k 1 ,1 (x + 1,1 ) + ′ i,j ∪{x i } (z) + d S ′ i,j ∪{x i } (x + 1,1))

			k 2
			j=2 (d S ′ 1,j ∪S ′ k 1 ,j ∪{u j } (z)
		k 1 -1	k 2
	+ d S ′ 1,j ∪S ′ k 1 ,j ∪{u j } (x + 1,1 )) +	i=2	j=1 (d S

f -connected.Recently, Li, Maezawa, and Tian proved a stronger result as follows.

Proof. Suppose that there is a good pair {a jmax+1 , b jmax+1 } of two vertices in L(v jmax+1 ) such that both a jmax+1 and b jmax+1 are not adjacent to one of vertices in U jmax . By Claim 2.3.1, there exist vertex sets A = {a jmax+1 , . . . , a m } and B = {b jmax+1 , . . . , b m } satisfying conditions (i)-(iii) of Claim 2.3.1. Since the vertex in I ′ ∩ L(v m+1 ) is degree one in H, one of a m and b m , say a m , is not adjacent to the vertex in I ′ ∩ L(v m+1 ) in H. Let u jmax be a vertex in U jmax not adjacent to a jmax+1 . Since U 0 ∩I ′ ̸ = ∅ by Claim 2.3.4 (i),

then for any good pair {a jmax+1 , b jmax+1 } of two vertices in L(v jmax+1 ), both a jmax+1 and b jmax+1 are not adjacent to one of the vertices in U jmax . This contradicts Subclaim 2.3.4.1. Hence we may assume that Then G has an f B -fractional colouring.

We begin by showing that Theorem 57 has the following result as a corollary.

Corollary 3

Let G be a triangle-free graph, and let

11/28 if v is special and has a special neighbour,

Proof. Let G ′ be obtained from G by deleting all vertices of degree at least 4. Since the demand of the vertices of degree at least 4 in G is 0, and since the demand of a vertex increases if its degree decreases (as can be seen by the definition of f G ), any f G ′ -fractional colouring of G ′ is in particular an f G -fractional colouring of G. Therefore, in the rest of the proof, we may assume that G is subcubic (its maximum degree is at most 3).

Indeed, the vertices v ∈ C are all special, hence we have demand Let G be the subgraph of G induced by the vertices of degree 2 or 3.

We may apply Theorem 57 in order to obtain an f B -fractional colouring of G; this is a random independent set

We observe that the vertices in V (F ) are precisely the special vertices which have (at least) one special neighbour. For each such vertex v, we recall that There remains to treat the case of vertices of degree 0 or 1. For every vertex v such that P [v ∈ I 0 ] > f G (v), we remove it from I 0 with probability 1 -f G (v) P[v∈I 0 ] ; this yields a new random independent set I 1 where P [v ∈ I 1 ] = f G (v) for every vertex v of degree at least 2. We construct I 2 by adding to I 1 all isolated vertices, as well as one extremity chosen uniformly at random from each isolated edge, and finally every other vertex v of degree 1 whenever it is uncovered by I 1 . It is now straightforward to check that I 2 is indeed a fractional f G -colouring of G.

. A description of the probability distribution

We are now ready to describe our fractional colouring procedure for a given triangle-free graph G of maximum degree 4. We will use the GFCA with a probability distribution over the independent sets of any induced subgraph H of G obtained as follows.

(i) We fix some real value λ > 0 (which will be optimised later on). We let I 0 be drawn according to the hard-core distribution at fugacity λ over the independent sets of H. Let us write this I 0 ← hc λ (I (H)).

(ii) We let H := H \ N [I 0 ] be the subgraph of H induced by the vertices uncovered by I 0 . We apply Corollary 3 to H in order to obtain an f H -fractional colouring I 1 of H.

(iii) We return the random independent set I 0 ∪ I 1 .

It turns out that this procedure is not enough to guarantee that χ f (G) < 3.5.

In order to fall below that threshold, we need to alter our last step and give a non-zero demand f (v) for some vertices v of degree 4, namely the ones which have at least one degree-4 neighbour. Before describing how to do that, we describe the analysis of the current procedure. We will then explain how to alter it gradually in order to obtain the promised upper bounds on χ f (G).

. The analysis of the probability distribution

Let G be a graph given with a function φ which maps each subgraph H from a given family of subgraphs of G to a random independent set of H. We introduce some notation to bound from below the marginal probabilities associated with φ on a vertex of given degree.

Definition 17. For every integer

To avoid a non-uniform behaviour of the probability distribution we construct over the independent sets, we will always make it so that µ φ is a non-increasing function over the integers.

Next, we introduce the notion of refined constraint, which will be helpful to compute constraints generated by a random independent set I = I 0 ∪I 1 constructed in two steps, where I 0 follows the hard-core distribution.

-On (2,k)-Hamilton-connected graphs

In this chapter, we introduce our work on (k 1 , k 2 )-Hamilton connected graphs.

. Introduction

Motivated by spanning connectivity and k-fan connected graphs, we define (k 1 , k 2 )-Hamilton-connected graphs.

Recall that a graph G is Firstly, we give a sufficient condition for a graph to be

Moreover, the bound of σ 2 (G) is sharp.

We construct a graph to state that σ 2 (G) ≥ n + k -2 of Theorem 58 is sharp as follows. Let k and m be integers with m ≥ 3k -2. Let G be a graph of order

can not find 2k internally-disjoint paths connecting x i and u j for 1 ≤ i ≤ 2 and

Another result obtained is about (k 1 , k 2 )-Hamilton-connectivity which is also a tight sufficient condition.

Hence we have

Let G * be the subgraph of G with

Let G be a graph satisfying the conditions of Theorem 58. For any pair of vertices x and y of G, let U = {u 1 , u 2 , . . . , u k } be a subset of V (G) \ {x, y}. By Lemma 8, it follows that there exist 2k internally-disjoint paths P 1 , P 2 , . . . , P k , Q 1 , Q 2 , . . . , Q k connecting {x, y} and U where P i is the path connecting x to u i and Q i is the path connecting y to u i for 1 ≤ i ≤ k. Let

and

Let S = ∪ 1≤i≤k S i be the union of k internally-disjoint paths connecting x to y

we call the path P ab a segment of S. For any segment P ab , we denote aHb a path connecting a and b through H. For any segment, the order of a segment is at least 3 by the maximality of S.

Let P ab be a segment of S such that N G (V (H)) ∩ P ab = {a, b} and w be an internal vertex of P ab , if there exist two vertices c, d ∈ N G (w) such that cd ∈ E(S) \ E(P ab ), then w is called an insertable vertex of P ab , and we call w Claim 4.2.6 There exists a segment in

|V (S)| ≥ 2k + 1, then for any vertex v ∈ V (H) and any (2k + 1)-subset W = {w 1 , w 2 , . . . , w 2k+1 } of V (S), there exists a (v, W )-fan of G. For each path from v to w j with 1 ≤ j ≤ 2k + 1, let w ′ j be the first vertex such that w ′ j ∈ S. By the pigeonhole principle, at least two of them belong to the same P i or Q i . It implies that there exists a segment in P i

By Claim 4.2.5 and Claim 4.2.6, without loss of generality, we assume that

which has a neighbour in H, and w is a non-insertable vertex of

. . y m where y 0 = r 1 and y m = w. For any vertex z ∈ N G (V (H)) ∩ V (S 1 ) \ {r 1 }, let z + be a successor of z in S 1 . We obtain the following claim. Claim 4.2.7 y i is not adjacent to z + for 1 ≤ i ≤ m. Proof. By induction on i for 1 ≤ i ≤ m. Suppose that z + y 1 ∈ E(G).

Then S + z + y 1 -r 1 y 1 -zz + ∪ r 1 Hz is the union of k internally-disjoint paths connecting x to y. The order of these k internally-disjoint paths at least |V (S)| + 1, a contradiction. We suppose that this claim holds for 1 ≤ j ≤ i -1 with i ≥ 2. Suppose z + y i ∈ E(G). Let T be a resulting graph of S after using a segment insertion SI[P 1 [y 1 , y i-1 ]]. It follows from the induction hypothesis of this claim that y j is not inserted by

By Lemma 7 and Claim 4.2.8, we have

2 , y])) + = ∅. By Lemma 7 and Claim 4.2.8, we have

Since σ 2 (G) ≥ n + k -2, by (4.3), (4.4), (4.6), (4.12) and (4.13), we have

This is a contradiction. Now we finish the proof of Theorem

and the orientation of

). Let v be any vertex of V (H).

We note that

Hence we have

Let r + 2 be the successor of r 2 in T 1,1,k 1 . By Claim 4.3.5, wr

We have the following facts likewise the analysis of (4.3), (4.4), and (4.6):

For 2 ≤ j ≤ k 2 , we have

We now infer that

This is a contradiction.

The proof of Theorem 59 is completed. 2

4.4 . Algorithm to find a spanning (X, U )-connection given two disjoint vertex subsets X = {x, y} and while there is a segment

if there is a non-insertable vertex w in I then Find the path from x to y through w and the vertices outside S.

else Do the segment insertion on I.

We present an algorithm to find a spanning (X, U )-connection given two disjoint vertex subsets X = {x, y} and U = {u 1 , u 2 , . . . , u k } with k ≥ 2 for a graph satisfying the condition of Theorem 58 as follows. The time complexity of the algorithm is O(kn 2 ) + O(n 3 ).

Motivated by a frequency assignment problem in cellular networks, Even, Lotker, Ron, and Smorodinsky [START_REF] Even | Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks[END_REF] introduced the notion of conflict-free colourings of hypergraphs. A colouring σ of a hypergraph H is conflict-free if for every edge e ∈ E(H) there exists a colour appearing exactly once in e. Pach and Tardos [START_REF] Pach | Conflict-free colourings of graphs and hypergraphs[END_REF] studied this notion and proved that every hypergraph with fewer than s 2 edges (for some integer s) has a conflict-free colouring with fewer than s colours.

Kostochka, Kumbhat, and Luczak [START_REF] Kostochka | Conflict-free colourings of uniform hypergraphs with few edges[END_REF] further studied conflict-free colouring for uniform hypergraphs.

A proper conflict-free colouring of G (pcf-colouring for short) is a proper colouring of G such that for every non-isolated vertex v, there is a colour appearing exactly once among the neighbours of v. We let χ pcf (G) be the smallest integer k such that there exists a pcf k-colouring of G. This notion is the combination of proper colouring and the pointed conflict-free chromatic parameter introduced by

Cheilaris [START_REF] Cheilaris | Conflict-free coloring[END_REF].

The notion of pcf colourings of graphs was formally introduced by Fabrici, Lužar, Rindošová, and Soták [START_REF] Fabrici | Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods[END_REF], where they investigated the pcf colourings of planar and outerplanar graphs, among many other related variants of a proper conflict-free colouring. They proved that χ pcf (G) ≤ 8 for all planar graphs and χ pcf (G) ≤ 5 for all outerplanar graphs. Plenty of further studies in pcf colourings of sparse graphs can be found in [START_REF] Caro | Remarks on proper conflict-free colorings of graphs[END_REF][START_REF] Cho | Proper conflict-free coloring of sparse graphs[END_REF][START_REF] Fabrici | Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods[END_REF][START_REF] Hickingbotham | Odd colourings, conflict-free colourings and strong colouring numbers[END_REF][START_REF] Liu | Proper conflict-free list-coloring, subdivisions, and layered treewidth[END_REF].

Caro, Petruševski, and Škrekovski [START_REF] Caro | Remarks on proper conflict-free colorings of graphs[END_REF] proposed the following conjecture about pcf colourings.

Conjecture 7 (Caro,Petruševski,Škrekovski [23,Conjecture 6.4]) If G is a connected graph of maximum degree ∆ ≥ 3, then χ pcf (G) ≤ ∆ + 1.

As a first step toward their conjecture, Caro, Petruševski, and Škrekovski [START_REF] Caro | Remarks on proper conflict-free colorings of graphs[END_REF] proved that for such a graph Note that the papers marked with * form the main content of this thesis. Other papers are introduced briefly in Appendix.

Appendix

Some of my works are not included in this thesis (see [START_REF] Dai | Strong list-chromatic index of subcubic graphs[END_REF][START_REF] Dai | New bounds for odd colourings of graphs[END_REF][START_REF] Dai | Properly colored cycles in edge-colored complete graphs[END_REF][START_REF] Ouyang | A hypergraph approach for logic-based abduction[END_REF]), which have been (or will be) contained in theses of my collaborators or my master's thesis. I introduce these works briefly here.

(1) We study strong k-edge-colouring of subcubic graphs in [START_REF] Dai | Strong list-chromatic index of subcubic graphs[END_REF]. A strong k-edge-colouring of a graph G is an edge-colouring with k colours in which every colour class is an induced matching. The strong chromatic index of G, denoted by χ ′ s (G), is the minimum k for which G has a strong k-edge-coloring. In 1985, Erdős and Nešetřil conjectured that

, where ∆(G) is the maximum degree of G. When G is a graph with maximum degree at most 3, the conjecture was verified independently by Andersen and Horák, Qing, and Trotter. In this paper, we consider the list version of strong edge-colouring. In particular, we show that every subcubic graph has strong list-chromatic index at most 11 and every planar subcubic graph has strong list-chromatic index at most 10.

(2) We consider odd colouring of graphs [START_REF] Dai | New bounds for odd colourings of graphs[END_REF]. A proper vertex-colouring of a graph G is said to be odd if for each non-isolated vertex there is a colour appearing an odd number of times on its neighbourhood. The odd chromatic number (3) As an analogy of the well-known anti-Ramsey problem, we study the existence of properly coloured cycles of given length in an edge-colored complete graph in [START_REF] Dai | Properly colored cycles in edge-colored complete graphs[END_REF]. Let pr(K n , G) be the maximum number of colours in an edge-colouring of K n with no properly coloured copy of G. In this paper, we determine the exact threshold for cycles pr(K n , C l ), which proves a conjecture proposed by Fang, Győri, and Xiao, that the maximum number of colours in an edge-colouring of K n with no properly coloured copy of

, where C l is a cycle on l vertices, l -1 ≡ r l-1 mod 3, and 0 ≤ r l-1 ≤ 2. It is a slight modification of a previous conjecture posed by Manoussakis, Spyratos, Tuza and Voigt. Also, we consider the maximal colouring of K n whether a properly coloured cycle can be extended by exact one more vertex.

(4) We present a hypergraph approach for logic-based abduction in [START_REF] Ouyang | A hypergraph approach for logic-based abduction[END_REF].

Abduction reasoning, which finds possible hypotheses from existing observations, has been studied in many different areas. We consider an abduction problem that takes into account a user's interest. We propose a new approach to solving such an abduction problem based on a hypergraph representation of an ontology and obtain a linear algorithm for a description logic.