Soutenance de Thèse – Thesis Defense
Coloration de graphes dirigés – Digraph Colouring
Lucas Picasarri-Arrieta (Université Côte d’Azur, CNRS, i3S)
Cette thèse a été réalisée dans le pôle Comred du laboratoire i3S, sous la direction de Frédéric Havet.
Abstract :
Erdős and Neumann-Lara introduced a notion of colouring of digraphs in the late 1970s, namely the dicolouring, and its associated digraph parameter: the dichromatic number. It appears in the last decades that many classical results on graph colouring have directed counterparts using these notions. This thesis focuses on both the extension of graph colouring results to digraphs, and their possible strengthenings on specific class of digraphs. In particular, we study directed analogues of Brooks’ theorem, density and structure of critical graphs, and reconfiguration of graph colourings.
Ce travail a bénéficié d’une aide du gouvernement français, gérée par l’Agence Nationale de la Recherche au titre du Plan d’investissement France 2030, dans le cadre du projet “UCA DS4H” portant la référence n° ANR-17-EURE-0004.
👉 En savoir + sur les thèses financées par l’EUR Systèmes Numériques pour l’Humain : https://ds4h.univ-cotedazur.fr/recherche/theses-financees-1
[Music] I will present some results I obtained during my thesis and the subject of my thesis was diagraph coloring and it was supervised by frederi a and cised by Stefan B and first let me recall to everyone what is a coloring of a graph so proper coloring of a graph is a coloring of its vertices so that when you have two adjacent vertices so two vertices link linked with an edge then they receive distinct colors and what we call the chromatic number of a graph is the minimum number of colors we need to find a proper coloring of this graph and we say that is a proper K coloring if we only use atmost K colors so on this example the chromatic number is three so you see it is Atmos three because indeed we have a proper three coloring of this graph and it is at three because you have a note cycle here and a not cycle you need at least three colors now for diagraphs uh we we will talk about D colorings and the D coloring is coloring of the vertices so that each color class induces an nylic sub diagraph or in other words every directed cycle uses at least two distinct colors so this is an example of a three D coloring of a diagraph so you see here that we have a directed cycle so we must use two colors on it and you see here that we have a cycle but it is not directed so we are allowed to use only one color and finally not that when we have what I call a Diagon so two arcs in the opposite directions between the same pair of vertices then we need two distinct colors for these vertices and what we call the diomatic number of a diagraph is again the minimum number of colors we need to find the D coloring of these diagraph so in this example the dimatic number is three and this this is at most three because we indeed have a three di coling it is exactly three because you see that we have a bir directed triangle here and on these vertices we need three distinct colors and these two Notions generalize the ones of proper coloring and chromatic number for undirected graphs just because if you take any graph and then you look at the diagraph you obtained by replacing every Edge by a Diagon then the proper colorings of the initial graph exactly the D color of the obtaining diaph and in particular the chromatic number is equal to the diomatic number and then if you think about any result on graph coloring in fact you can see it as a result on die colorings of bir directed graphs which are the diagraphs in which every Arc is in a Diagon and then two questions naturally arise the first one is is this result on B graphs true not only for btic graphs but for all diagraphs so can we generalize it to all diagraphs or not and if we can can we strengthen it on a disjoint class of diagraphs and usually we look at oriented graphs which are the Diagon free diagraphs so diagraphs without any Diagon and these were the two main questions I considered during my thesis and I would like to start by illustrating these two questions with two emblematic results on graph coloring and the first one is the strong perfect graph theorem due to chovi and for this I need a few definition so what we call the chromat The Click number of a graph is the size of a largest click in the graph where click is a set of pairwise edes and vertices and what is clear is that the click number the chromatic number is always at least the click number just because when you take proper coloring you need to use distinct colors on every vertex of the click and we say that the graph is perfect if in fact equality holds not only for this graph but for each of its induced sub subgraphs and then if we look for necessary conditions for a graph to be perfect then we see that it cannot contain a DOT hole which is an induced cycle of OD length and of OD lengths at least five because in this case The Click number is two but the chromatic number is three and also it cannot contain a node anti hole which is just the complementary of a node hole because in this case a click number is a number of vertices minus one number two and the chromatic number is one more so we have a necessary condition for a graph to be perfect it cannot contain one of these two obstructions in fact the strong perfect graph theorem says that this easy condition is indeed sufficient so this is an exact characterization of perfect graphs and then we can ask what is up what is happening for diagraphs so now what we call the big click number is a size of a largest B click where a b click is a set of vertices that are per wise linked with a a Diagon and again we have that the diomatic number is at least the B click number and we say that the diagraph is perfect if equality holds between the dimatic number and B number not only for this diagraph but for for each of its induced sub diagraphs and again we can find necessary conditions for a diagraph to be perfect the first one is it cannot contain a birir hole which is obtained from uh n Hole by replacing every Edge by a Dion and then we are allowed to put some ARS but these codes cannot be Diagon it must be simple ARs and then we have we cannot have a b directed antile which is obtained in the same way from a n anti hole and again we can put simple ARs here but not noon there is a new obstructions uh which are induced directed cycle of length at Le three because in this case the biglick number is one we don’t have any Diagon but we indeed need two colors for it because it is not a cyclic so we again have this necessary condition for a diagraph to be perfect and it turns out that this is also NE sufficient condition so it’s an exact characterization of perfect diagraphs this is a result of Andres and hor tler and this illustrates the first question we had we have a result on graph coloring and we generalize it to di graphs and the second question would be what can we say about oriented graphs and in this case it is not so interesting we just have that an graph is perfect if only if it is ayclick and now I would like to consider another emblematic result on graph coloring for which we will have the opposite the first question will be easy but the second will turn out to be challenging so the Four Color theorem say that every PL graph has chromatic number at most four and from this we directly obtain that every planer diagraph has dimatic number at four this is just because if you have a planer diagraph you can forget its orientations you just see it as a graph and you can color it into independent set with four colors and these independent set for sure here basically Sub sub diagraph and of course this is best possible just because a complete bed graph on four vertices needs four colors but then we can ask what is happening for oriented graphs and this is one of the most celebrated conjecture on the diomatic number which says that in fact the diomatic number of every oriented plane graph should be at most two this is a conjecture of no man and uh we know it is at most three just because of the low density of plan graphs but for two it is open so these two examples illustrate the interest of these two questions I consider during my thesis and I consider them with many classical result on graph coloring and today I will first talk briefly about some result I obtained on di critical diagraphs and uh also about diagraph with I coloring and then I will talk in details about the Brooks theorem and its generalizations so let’s start with dial diagraphs so we say that a diagraph is K di critical if it’s diomatic number is K but if you remove any Arc or any vertex its diomatic number decreases to K minus one so these diagraphs are somehow the minimal obstruction to the K minus one diability and then we Define in the same way uh that the graph is K critical if it has chromatic number K but if you remove an x a Vertex or an edge increases to K minus one and for these particular graphs and diagraph a natural question is to ask what is the minimum density of such graphs and diagraphs and for this we introduced GK of n which is just the minimum number of edges in a kritical graph on N vertices and the same way we Define DK of n which is a minimum number of ARS in a k dial diagraph on N vertices and okay of n which is just the same for oriented graphs and we directly obtain some easy bonds by definition the first one is that GQ of n is always atmost twice GQ of n this is because if you have a k critical graph and you replace every Edge by a Diagon you obtain a k di critical diagraph for which the number of arcs is twice the number of edges of the original graph the second one is that ok of n is at least GK of n this is just because every oriented graph is a Di and CIT uh introduced the study of the functions DK and OK and then made two mainly two conjectures on this topic related to these two easy inequalities the first one is that in fact there should be equality between DK of N and twice GK of N and moreover they conjecture that the sparest K dial diagraphs must be bir directed so these must be exactly the DI critical diagraphs obtained from sparse critical graph by replacing the edges by diagonals and they made second conjecture which is that there should be a significant gap between OK and DK so o of n should be at least 1 plus some Epsilon time D of N and both conjectures are still open and what is known on this topic uh is the following so in the uned case almost everything is done so there is a famous Bond due to koson that they obtain with the potential method which is almost best possible in the sense that this is the exact value of GK of n for every fixed K and infinitely many values of n so almost everything is done and then we can look at the recer form of the first conjecture of cibit because if DK of n is twice DK of n then in particular it should be at least this and already this is open and this is not only this is not only for low values of K and the best bound we know in general is due to Abul and Vermon and it is closed to the conjectured one but you see that we still have a a gap of roughly n / two and for the second conjecture all the cases except the case k 3 is are open and my contributions to uh this topic are the following in a first work with Michael tiits we gave the exact value of DK of n when n is not too large compared to K so n is between K and 2 K minus one in this case we are able to give the exact value of DK of N and so this generalizes a result of galy and we are also able to characterize exactly the K dial diagraphs on N vertices with exactly DK of n AR and this confirms completely the first conjecture of cits in this particular case and in a second work with frederi a and cloo we gave a general result on four di critical diagraphs using the potential method which mainly has two two consequences the first one is a lower Bor on d4n which was already known but we also characterize exactly the dial diagraphs with exactly this number of arcs so this confirms the first conjecture for the case k equal 4 and the second main consequence of our general result is a an answer to the second conjecture for k 4 which is that there is a significant gap between o4 and D4 so a gap of roughly n/ 51 now I would like to uh briefly talk about the second important part of my thesis which is the notion of diagraph red coloring and for this I need the introduction of an auxiliary graph so given a diph d what we call the K doring graph of D is the undirected graph in which the vertices are all the k d colorings of D and there is an edge between two colorings if they differ on exactly one vertex Okay so for instance this is the two die coloring graph of the directed triangle and then we can Define the K coloring graph of an Ned graph in the same way but taking proper colorings instead of D colorings and what we call a recoloring sequence of a diagraph is a path in this case D coloring graph so it can be seen as a sequence of D colorings such that when you take two consecutive colorings they differ on exactly one vertex and we say that di graph is K mixing if its K ding graph is connected so for any pair of K diing you indeed have a recoloring sequence between them and the main questions we consider on this topic are first given a dph d can we have a guarantee that it is K mixing for some integ K and secondly if it is K mixing can we also find a Bonds on the diameter of the K doring graph so we know that not only for only pair of D colorings you have a recoloring sequence between them but also that it must be short it cannot be long and so what is known on this topic well for undirected graphs these questions have been considered by Bon M sesa and dial who independently proved that if you take a number of colors which is at least the degeneracy of your graph plus two then your graph must be K mixing for this number of colors K where the D is the least integer D such that you can eliminate the vertices of your graph one after the other by eliminating vertices of the atmos B and CA made a celebrated conjecture that not only with this number of colors uh G must be K mixing but also the diameter should be bonded by a quadratic function in the number of vertices of G and this is still open and the best results towards this conjecture are due to BU and hinish who proved that first we have a polinomial bond in the number of vertices when the the deacy is fixed and secondly if we increase the number of colors to three half times the deacy plus one then we indeed obtain a quadratic diameter and bu and perano proved that if we even increase the number of colors to twice genery plus one then we obtain a linear diameter in the number of vertices and in a first work with Nicola bu freder niol anden we consider the same question for diagraphs where the D the the same Notions but you take the degree of a Vortex to be the minimum between its in and out degrees and we Pro that with this number of colors uh your diagraph must be K mixing and we made the same conjecture that we indeed should have quadratic diameter of the K decoring graph in the number of vertices and then we proved that if we increase the number of colors to 3 half * D plus one we indeed obtain a quadratic diameter if we increase it to twice de +1 we obtain a linear diameter so you see that we generalized everything but the general Bond the general polinomial bond in n and this we managed to obtain it later with nicolan n and ignis in a second work now I would like to talk in details about Brooks theorem and its generalizations so Brook theorem says that if you have a connected graph then its chromatic number is always at most its maximum degree unless it is one of the following obstructions so either an not cycle in which case the maximum degree is two but you indeed need three colors or a complete graph in which case the maximum degree is the number of vertices minus one but you need need one color per vertex and then again you can ask what is happening for diagraphs and for this you first need a definition of the maximum degree in a diagraph so we will first consider the maximum of degree of a diagraph to be Delta Max of D which is the maximum on every vertex of the maximum between its in and out degrees and with this definition Mo obtain a generalization of book theorem it says if you take a connected diagraph then it dimatic number must be at most Delta Max unless this is one of the following obstructions so of course we find the two same obstructions so a bidirected cycle a bidirected complete graph and there is a new one which is uh directed cycle in this case Delta Max is one but we inde need uh two colors and this generalizes the result of Brooks when we look at it on by directed graphs and this is an example of a generalization of Brook theorem but this is not the only one and in particular there is a result about list coloring due to Borodin and eral so in the concept of list coloring every Vortex receives a list of available colors and what you want is to find a proper coloring of your graph such that the color of every vertex belongs to its list of available colors and now if you have a list assignment such that the number of available colors on V is always at least the degree of v on every vertex V then your graph must be L colorable for this list assignment L unless it is a g tree where G tree is any graph for which each block is an obstruction of Brook theorem so a complete graph or not cycle and from this you can obtain Brook theorem by Say by saying the list on every vertex is just all the integers from one to the maximum degree Delta uh and then okay this is not hard but you can check that you can obtain Brook theorem from it and again we can ask what is happening for diagraphs and this is a result of haran and MOA that now if you have a list of available colors on every vertex of a diagraph such that the number of available colors is at least the maximum between the in and out degrees then our diagraph must be unless it is a directed Galla Tre where directed Gall Tre is any diagraph for which every block is an obstruction of the directed book theorem so either bed complete graph aired cycle or just a directed cycle and these are examples of generalization of book’s theorem and we can represent them on this diagram so there is an arc from theorem a to theorem B whenever theorem a generalizes theorem B but these are not the only one in particular there is a result about partitioning graph into degenerate subgraphs due to Bodin and then we can ask for a common generalization of these two independent results and this has been done by Bodin Nal when they produced the notion of variable degeneracy and then what we want is to find a common generalization of these two independent results and this has been done by Bens andal when they introduced the notion of variable degeneracy for diagraphs and in a work with Daniel gonalves and Amad reenal we proposed another definition of the variable genery of a diagraph that we called B variable genery uh and we Prov the analog of Brook theorem with this notion which generalizes the one of M Nal so it generalizes all these results and it’s interesting not only from a structural point of view but also from an algorithmic point of view because all these results are of the form if I have a graph and I have this number of colors I can always Color My Graph in such a way that each color class satisfies some property unless my graph is one of the following obstructions but then a natural question is how hard is it to actually compute this coloring and usually all these proofs give a polinomial Time algorithm so the natural question is whether we can obtain linear time algorithms and this was open for the variable de cases and we indeed give a general framework to obtain linear time algorithms for all these problems here I would like to give you the statements but I first need a few definitions so if I have a diagraph d and a function f which Associates to every vertex of D to integers then we say that D IS F if for every nonm sub diagraph h of D I can find the vertex V so that its IND degree is less than the function f minus on V and the L degree is less than f+ of V where f+ and F minus F minus and f+ are respectively the projections on the first and second coordinates of the function f so how can we use it for instance we can say that the diagraph is acyclic if only if it is f de generate where f is a function constant equal to one one this is just because when you have a diagraph it is asli if only if for every nonm sub diagraph we can find a Vertex with in degree zero or out degree zero now that if we have a sequence of functions F1 to FS we say that this is folable if we can color the vertices with colors from one to S such that the vertices colored I induce an fi generate sub diagraph so let me give some example so for instance we can modelize doring we just say that a dimatic number of a diagraph is at most s if only if this F diable where f is a sequence of s function and each of this function is constant equal to one one but we can also modelize list doring by saying that fi of V is equal to 1 one if color V is available for V if color I is available for V and z z otherwise and not that if f i of V is 0 0 then we cannot color V with color I otherwise when we look at the the induced diagraph which is just induced by V then you cannot eliminate the only vs V because this is z and zero and this is not less than zero now I need to Define what is a hard pair and these will be the obstructions in our statement the same way that we have some obss in Brooks theorem and we will constrict them inductively so first we say that DF is a hard pair if one of the following hold so D might be any diagraph but we have only one function that is not constant equal to zero and uh this unique function is equal to the in degree and the out degree of the vertex for each so this is an example of Harper so you see that we only have one available color so we are forced to color all the vertices in red but then if they are all colored red this is not NE di coloring because you cannot eliminate any vertex because you have okay you have that the the in degree is exactly F minus and the out degree is exactly f+ and then we find the same obstructions as in Brooks theorem so D might be a b directed cycle and we have exactly two functions that are not constant equal to 0 0 and they are constant equal to one one and in this case we’re just trying to two color on not cycle so this is not possible and finally D might be a bidirected complete graph but and then we have that all the functions must be constant symetric so the first coordinate is equal to the second coordinate and they must sum to this number of vert minus one so this is an example you see that you cannot color two vertices in red otherwise these vertices do not induce a one one generate sub graph and for the same reasons you cannot have three vertices in green so you cannot color it and these are the three basic blocks of our obstructions and then we can construct larger hard Pair by saying that if we have two hard Pairs and we just glue them on a vertex and on this vertex we just sum the functions per yse coordinate then what we obtain is again a harp PA and we can continue like this to obtain larger and larger hot Pairs and again we can easily check that uh the diagraphs the pairs we are constructing are not colorable and our result is the following so if you have a if we have a connected diagraph and a sequence of functions then we need a notion of color Budget on every vertex so for list coloring it was the number of available colors is always at least the degree now we have that the sum of the functions on the first coordinate is always at Le in degree of the vertex and the sum of the functions on the on the second coordinate is always at least the O then if we have this condition D must must be F directable unless it is a hard PA so these are exactly the the obstructions in fact it is if only if then if we look at the consequences well if we restrict this result to symmetric function so the first coordinate being equal to the second coordinate we obtain exactly the result of B and if we F assume that our functions are valued in 0 0 or 1 one we are just modelize list Ding and we obtain the result of howun and MOA and if we further assume that all the functions are constant equal to one one then we are just modalizing list deing and we can obtain the directed Brooks theorem now I would like to show you the proof and the main tool for the proof is the following observation imagine that we have a Vertex V and we decided to color V with color I and this is Possible only if f i of V is not z0 otherwise we cannot color V with color I and then we just want to remove V and remember that it is colored I and for this we just have to update the color Budget on every neighbor of V so they remember that they have a neighbor colored I and in fact we’ll just update the color budget for color I so every in neighor of V will decrease its functions by 01 so it reme it remembers that it has an out neighor colored ey and every out neighbor uh will decrease its function fi by one zero and every neighbor which is both out and in neighbor will decrease it by one one and then you can easily show that if you have an F Prime doring of D minus V you can extend it into an FD coloring of d by coloring V with color I and this is the main tool and now let’s see a sketch of the proof so we have DF which is a non hard pair then the very very first type consists of redu ing to the case where we only have two colors and for this we just say that the first colors will be fi for some well chosen I and F2 Prime will be the sum of the other functions then you can show that if you choose I carefully what you obtain here is again a non hard pair and that using a greedy procedure you can transform an fime doring of D into an F doring of D then what we want is to reduce to another hard pair for which the diagraph is too connected so assume that we have a cut vertex in the underlying graph of d uh then we just want to color one part of the diagraph and reduce to the to the other part uh and for this okay we just uh take a sping so let’s say we want to color the left side then we take a spining tree of the left side rooted in X and we color the vertices from the leaves to the root and using the fact that when we color vertex it has a non col neighbor we can always justify that one of color two or or one must be available for this vertex such that the vertices color B induce an F1 generate sub diagraph and ver is called to induce an F2 sub diagraph then we have to remember that X has some neighbor already colored so we update the first function by decreasing the first coordinate by the number of in Neighbors colored one and then second coordinate by the number of out neighbors col one and then we update the second function by decreasing by the number of in Neighbors color two and the second coordinate by the number of out neighbors color two and then we can continue this process unless what we obtain here is a hard pair and if this is the case we just do the opposite so we color the right side and if this is again a hard pair then we have a contradiction because we have two hard pairs glued an X and this is again a hard pair so if we continue this process we will manage to obtain a smaller pair for which the D graph is too connected and then the third and fourth steps consists of proving that we can assume that both colors must be available on every vertex and that our di the underlying graph of our diagraph is not just a cycle the idea is that if one of these two properties is not true then we can directly find an N di coloring of our diagraph and then now we can separate two cases the first case is we have a Vertex V so that when we remove it our diagraph Remains Two connected and in this case we just want to color V with let’s say color one and to update the colors on its neighbors uh in such a way that what we are reducing to is a non hard pair but we know that it remains too connected so it is easy to detect if it is a hard pair or not and if it is a hard pair then we use the fact that both colors are available for V and we just color V with the other color and this is a bit of case analysis but you can show that one of these two colors must always be available for V so that we are not reducing to a hard PA and if we don’t have such a Vertex that we can remove then using an analog of ear decomposition we can show that in our diagraph in in the underlying graph there is a path p in which every vertex has degree exactly two in the underlying graph and when you remove it when you remove the path what you obtain is again two connected and then we just do the same so we try to color it so we use the fact that both colors are available on every vertex and we color the path with color 1 212 1 and we look at the reduced pair if it is hard pair then we color with the opposite and again we justify that one of these two choices must not reduce to a hard pair so this is the proof now I would like to come back to the directed Brook theorem and discuss some strengthening of this result so we call that it says that the dimatic number of a diagraph is always at most Delta unless it is an obstruction uh where Delta Max is a maximum on every vertex of the maximum between it in and out degrees but this is not the only definition of the maximum degree of a diagraph and for instance we can look at Delta Min which is the maximum on vertex of the minimum between in our degrees and using an easy G procedure we indeed have that the diomatic number is always at most Delta me plus one then a natural question is whether we can characterize the diagraphs for which the diomatic number is exactly Delta Min plus one which would be a strengthening of the result of moar because every diagraph for which equality holds with Delta Max is diagraph for which equality holds with Delta me so it would be a better characterization but there is little hope for such characterization because and this is a result of Abul and OB deciding if the dtic number is at most Delta me is already an MP complete problem so we cannot expect nether characterization of such of such a characterization but still we we can look for necessary conditions for diagraph to have dimatic number Delta Min + one and this is a contribution of mine that if a diagraph D has dimatic number exactly Delta Min plus one then one of the following holds first Delta Min is at most one and we cannot say anything for instance D might be a cycle with some cords or Delta Min is two and in this case D must contain a or Delta me is at Le three and in this case D must contain a b directed complete graph on S vertices bir directed complete graph on T vertices and every Arc from KS to KT where s and t sums to Delta Min plus one so we do not have a b directed complete graph on Delta plus one vertices but almost we’re allowed to have a cut for which the ARs are only going in One Direction and if we look at this the consequences of this result on oriented graphs then we directly obtain that if G is an oriented graph with Delta Min at least two then it’s D chromatic number is at most Delta Min and this is just because we’re excluding the first case by assuming that Delta Min is two and we are excluding the second and third cases because in both cases they must container Diagon and if we look at the very first consequence of this result we have that if you take a undirected graph with maximum degree atmost 5 and you fix an orentation of it then you obtain an oriented graph in which Delta Min is at most two and in particular it must be two D colable and this was already open before I would like to show you the proof because it is short so assume that we have a diph d for which the dtic number is exactly Delta me+ one then we’ll show that either Delta is two and D contains the Diagon or Delta is at least three and we have this bidirected complete graph dominating another bidirected complete graph so what we do is first we partition the vertices in two parts and in X we put every vertex with out degree Atmos Delta and in y we put every vertex with IND degree Atmos Delta if some vertex satisfies both inequalities we just put it arbitrarily in one side and then we make some Transformations on this diagraph so first we remove every Arc from y to X and then we replace the arcs from X to Y by Diagon and note that these two inequalities are still true because I just added AR from y to X and what I claim is that the diomatic number did not decrease and in fact this is because every D coloring of this this new diaph is also a doring of the previous one okay imagine that this is not the case so we have a monochromatic directed cycle in D then it cannot be a directed cycle in X otherwise it’s also a directed cycle of D Prime and it cannot be contained in y so it must choose an AR from X to Y which is a now Diagon so we have a monochromatic Diagon this the contration then we can extract in D prime a sub diagraph an induced sub diagraph H uh which is Delta + one vertex dial so whenever we can remove a Vertex such that the dimatic number remains at least Delta plus one we just remove it and then we know that in a dial Delta plus one di critical diagraph every vertex has in degree and out degree at least Delta this is just by minimality so these inequalities are now equalities in h and if we if we sum the out degrees in xh so the intersection between X and H what you obtain is exactly Delta times number of vertices in x H and this must be equal to the sum of the in degrees because what we are Computing is exactly the number of arcs inside xh plus the number of Dions between xh and YH and using the fact that every vertex has indre at least Delta we obtain that H must be Delta dular so every vertex has in degree and out degree exactly Delta and from this we can use the directed book theorem so we have that H has diomatic number exactly Delta Max of H + one so either Delta is two and H is a b cycle and one Diagon of H must be in YH or in xh so this is a Diagon of D or Delta is at three and H is a b directed complete graph and we th have a bir directed complete graph here dominating a bed complete graph here and we obtain the result now I would like to conclude with two further research directions the first one is a celebrated conjecture due to air and man which says that in fact for an ored graph the diomatic number should be sublinear in the maximum degree and this is open we don’t know okay we don’t have any sublinear bond and the best Bond approaching it is the existence of non-trivial multiplicative constant so the dimatic number of n g is always at most 1 minus Epsilon time delta T of G where delta T is the maximum of a vertex of the geometric mean between the in and out degrees so this is a parameter between Delta Min and Delta Max so this is a result of how and MOA and a very particular case of this conjecture that I don’t know how to solve is the case of uh okay imagine we take two complete graph on N vertices and we look at the square product so it is an N by n grid but instead of having a path on every row and every column we have a complete graph instead then if the conjecture is true uh every orientation of this graph should have uh dimatic number at most n over l n and this I don’t know how to to solve and if the conjecture is not true then this might be a candidate for disproving it and the second further resarch directions uh I would like to mention is related to a famous conjecture of boo which says that for every graph the chromatic number is at most the average between the maximum degree plus one and the click number and this is open and we just know it for small values of Epsilon so we know that for some Epsilon the chromatic number is always at most 1 minus Epsilon time Delta + one plus Epsilon times a click number and in a work in progress with kaashi uh we believe that the same holds for diagraph by taking the maximum degree to be this Delta til and the click number to be the bed click number and we managed to prove the analog of this result of read so the existence of Epsilon so that dimatic number is at most 1 minus Epsilon time the delt plus one plus Epsilon time the Blick number and what is nice is that if you look at this result on bidirected graphs you obtain the result of re and if you look at it oned graphs you obtain the result of the previous slide of AR and MOA and uh okay that’s all I wanted to say today thank you J noic [Music]