2015 - 2016

---

Vendredi 18 septembre 2015 - Homomorphism bounds for K4-minor-free graphs - Florent Foucaud.
Résumé : A homomorphism of graph G to graph H is a function h from V(G) to V(H) which preserves the edges, i.e. if u,v are adjacent in G, then h(u),h(v) are adjacent in H. Homomorphisms extend the classic notion of proper graph colourings. Given a graph class C, an interesting optimization question is whether there is a graph to which all members of C admit a homomorphism (this graph is called a bound for C). If there exists one, what is the smallest order of such a bound? For example, all planar graphs admit a homomorphism to the graph K4 (this is the Four Colour Theorem), but no smaller graph is a bound. In this talk, we discuss the related problem of determining bounds for planar graphs and their subclasses, with some additional girth restrictions. Our focus will be on K4-minor-free graphs, i.e. series-parallel graphs. This is joint work with Laurent Beaudou and Reza Naserasr.

Vendredi 25 septembre 2015 - La Nuit des chercheurs.

Vendredi 2 octobre 2015 - Light structures in sparse graphs with minimum degree 2 - Roman Soták.
Résumé : A graph $H$ is defined to be light in a graph family ${\cal{G}}$ if there exists finite number $w(H,{\cal{G}})$ such that each $G \in {\cal{G}}$ which contains $H$ as a subgraph, also contains its isomorphic copy $K$ with $\sum\limits_{x \in V(K)} \deg_G(x) \leq w(H,{\cal{G}})$. In this talk we will investigate light short paths in families of graphs with bounded average degree and light structures in families of plane graphs of minimum degree 2 with prescribed girth.

We will show that every graph with minimum degree at least 2 and average degree $ad (G) < \frac{14}{5}$ and every plane graph with minimum degree at least 2 and girth $g(G) \geq 7$ contains a light path on three vertices. Moreover we will give examples providing sharp bounds on $w(P_3)$ for families of graphs with prescribed $ad(G)$ or $g(G)$, respectively.

Further we will show that graph $K_{1,3}$ is light in the family of plane graphs of girth $g(G) \geq 7$, with $\delta(G) \geq 2$ and without adjacent 2-vertices, and $C_{10}$ is light in family of plane graphs of girth $g(G)=10$, with $\delta(G) \geq 2$ and without adjacent 2-vertices.

Vendredi 9 octobre 2015 - List star edge coloring of subcubic graphs - André Raspaud.
Attention cet exposé aura lieu en salle 76.
Résumé : A star edge coloring of a graph G is a proper edge coloring such that every 2-colored connected subgraph of G is a path of length at most 3. For a graph G, let the list star chromatic index of G, ch_s'(G), be the minimum k such that for any k-uniform list assignment L for the set of edges, G has a star edge coloring from L. Dvorak, Mohar and Samal asked whether the list star chromatic index of every subcubic graph is at most 7. We will give a partial answer to this question in this talk by proving that it is at most 8. We will also give some bounds for the list star chromatic index of sparse graphs.

Vendredi 16 octobre 2015 - Maintenance et simulation de graphes aléatoires dynamiques - Romaric Duvignau.
Soutenance de thèse dans l'amphi du LaBRI à 10h30.
Résumé : Nous étudions le problème de maintenir une distribution donnée de graphes aléatoires après une séquence arbitraire d'insertions et de suppressions de sommets. Dans l'objectif de modéliser l'évolution de réseaux logiques dynamiques, nous travaillons dans un modèle local où l'accès à la liste des sommets est restreint. À la place, nous faisons l'hypothèse d'un accès à une primitive globale qui retourne un sommet aléatoire, choisi uniformément dans l'ensemble total des sommets. Le problème de maintenance a été exploré sur plusieurs modèles simples de graphes aléatoires (graphes d'Erd?s–Rényi, graphes basés sur le modèle par paires, graphes k-sortants uniformes). Pour chacun des modèles, un ou plusieurs algorithmes pour la tâche de maintenance ont été décris et analysés; les plus élaborés de ces algorithmes sont asymptotiquement optimaux. Le problème de maintenance soulève plusieurs problèmes de simulation liés à notre contexte distribué. Nous nous sommes intéressé en particulier à la maintenabilité de distributions de graphes et à la simulabilité de familles de distributions de probabilité sur les entiers, dans le modèle d'aléa présenté. Une attention particulière a été portée sur la simulation efficace de lois spécifiques nous intéressant (certaines lois binomiales). Cette dernière a pu être obtenue en exploitant les propriétés d'un nouvel arbre de génération pour les permutations, que nous avons introduit.

Vendredi 16 octobre 2015 - i-Mark: A new subtraction division game - Eric Sopena.
Résumé : Given two finite sets of integers S ⊆ N \ {0} and D ⊆ N \ {0, 1}, the impartial combinatorial game i-Mark(S, D) is played on a heap of tokens. From a heap of n tokens, each player can move either to a heap of n − s tokens for some s ∈ S, or to a heap of n/d tokens for some d ∈ D if d divides n. Such games can be considered as an integral variant of Mark-type games, introduced by Elwyn Berlekamp and Joe Buhler and studied by Aviezri Fraenkel and Alan Guo, for which it is allowed to move from a heap of n tokens to a heap of ⌊n/d⌋ tokens for any d ∈ D.
Under normal convention, it is observed that the Sprague-Grundy sequence of the game i-Mark(S, D) is aperiodic for any sets S and D. However, we prove that, in many cases, this sequence is almost periodic and that the set of winning positions is periodic. Moreover, in all these cases, the Sprague-Grundy value of a heap of n tokens can be computed in time O(log n).
We also prove that, under misère convention, the outcome sequence of these games is purely periodic.

Vendredi 23 octobre 2015 - The N+-Perfect Graph Conjecture for Claw-Free Graphs - Annegret Wagler.
Résumé : The subject of this talk is the study of the Lovasz-Schrijver PSD- operator N+ applied to the edge relaxation ESTAB(G) of the stable set polytope STAB(G) of a graph. We are particularly interested in the problem of characterizing the graphs G for which N+(G) := N+(ESTAB(G)) equals STAB(G), called N+-perfect graphs, and to find an appropriate polyhedral relaxation of STAB(G) that coincides with N+(G) and STAB(G) if and only if G is N+-perfect. An according conjecture has been recently formulated (N+-Perfect Graph Conjecture); we verify it for the well-studied class of claw-free graphs.

Du 4 novembre au 6 novembre JGA à Orléans.

Vendredi 13 novembre 2015 - Symmetry Breaking in Graphs - Monika Pilsniak.
Résumé : The distinguishing index D'(G) of a graph G is the least cardinal d such that G has an edge colouring with d colours that is preserved only by the trivial automorphism. This is an analog to the notion of the distinguishing number D(G) of a graph G, which is defined for colourings of vertices by Albertson and Collins. We obtain a general upper bound $D'(G)\leq\Delta(G)$ unless G is a small cycle C_3, C_4 or C_5. We present also quite better bound for some classes of graphs: traceable graphs, claw-free graphs and 3-connected planar graphs.We derive several bounds for infinite graphs, in particular, we prove the general bound $D'(G)\leq\Delta(G)$ for an arbitrary infinite graph. Nonetheless, the distinguishing index is at most two for many countable graphs, also for the Cartesian product of denumarable graphs. In the second part of the talk we introduce the distinguishing chromatic index $\chi'_D(G)$ defined for proper edge-colourings of a graph G. A correlation with distinguishing vertices by colour walks is shown. We prove that $\chi '_D(G)\leq\Delta(G)+1$ except for four small graphs C_4, K_4, C_6 and K_{3,3}. It follows that each connected Class 2 graph G admits a minimal proper edge-colouring, i.e., with $\chi'(G)$ colours, preserved only by the trivial automorphism. Finally we show that this proper colouring breaking all non-trivial automorphism with $\Delta +1$ colours could be expanded for infinite graphs.

Vendredi 20 novembre 2015 - Incidence coloring : Cold Cases - Feri Kardos.
Résumé : Incidence coloring has been defined in the 90s as a strong coloring of vertex-edge incidences. In the first part of the talk, connections to other types of colorings will be presented. Then we will present a couple of results, obtained recently in cooperation with M. Macekova, M. Mockovciakova, E. Sopena and R. Sotak, covering som cases that had been left open in the previous works on this topic.

Vendredi 27 novembre 2015 - Présentation de Maths à modeler - Paul Dorbec.

Vendredi 4 décembre 2015 - On dense codes - Arnaud Pêcher.
Résumé : We consider the sphere packing problem in arbitrary dimension: what is the maximum fraction d_n of the Euclidean space Rn that can be covered by unit balls with pairwise disjoint interiors? d_n is known for only for some small values of n, and when n grows, we only have lower bounds. A trivial lower bound states that for every n, d_n >= 2^-n. Minkowski and Hlwaka's Theorem (1905) improved this lower bound by a factor 2. Asymptotic improvements of this bound were obtained (from Rogers, 1947 up to Ball, 1992), all of them being of the form d_n >= c n 2^-n where c is a constant. This problem has a natural reformulation in graph theoretic terms as follows: let G denote the graph whose vertices are the points of the Euclidean space and edges are pair of vertices at distance at most 2 one from the other. The independent sets of G are the sphere packings: so, finding a maximum-density sphere packing is the same as finding a maximum-density independent set in this infinite graph. By using graph theoretic arguments only, Krivelevich et al. established that d_n >= 0.01 n 2^-n for sufficiently large n (2004). In a recent breakthrough, Venkatesh introduced the first superlinear improvement: there are infinitely many n such that d_n >= c n log log n 2^-n, where c is a constant. Venkatesh's result is however non-constructive. In this talk, we focus on Bachoc and Moustrou's constructive proof of Venkatesh's lower bound.

Vendredi 8 janvier 2016 - Power domination in triangulations - Claire Pennarun.
Résumé : La domination de puissance dans les graphes est un problème qui provient de problèmes de surveillance dans les réseaux électriques. Le but de la domination de puissance est de surveiller tous les sommets d'un graphe donné, à l'aide d'un ensemble S de capteurs. On note M l'ensemble des sommets surveillés. La domination de puissance utilise le processus suivant:
- On place des sommets dans un ensemble initial S
- (domination) les sommets de S et leurs voisins sont ajoutés à M
- (propagation) un sommet de M se "propage" vers un voisin si c'est son seul voisin qui n'appartient pas à M. Ce voisin est ajouté à M.
L'étape de propagation se répète tant qu'on trouve un sommet à propager. On dit que S est un \emph{ensemble de domination de puissance} si M contient tous les sommets du graphe à la fin du processus. Le \emph{nombre de domination de puissance} de G, noté $\gamma_P(G)$, est la taille minimum de S. Le problème de détermination de $\gamma_P(G)$ pour un graphe donné a été prouvé NP-complet pour les graphes planaires. Un des obstacles à l'étape de propagation dans les graphes est la présence de certains sommets d'articulation. Nous nous intéressons donc naturellement aux triangulations (graphes dans lesquels toutes les faces sont de degré 3) car elles ne contiennent pas de tels sommets. Nous présentons une preuve que $\gamma_P(G) \leq \dfrac{n-2}{4}$ si $G$ est une triangulation à $n \geq 6$ sommets.

Vendredi 15 janvier 2016 - Coloration aléatoire de graphes peu denses - Marthe Bonamy.
Résumé : D'après le théorème de Brooks, le nombre chromatique d'un graphe est presque toujours inférieur à son degré maximum. En 1998, Reed a montré que cette borne pouvait être affinée de façon à remplacer le degré maximum par la taille d'une clique maximum dans une fraction de la borne. En d'autres termes, on peut toujours économiser un nombre de couleurs proportionnel à l'écart entre le degré maximum et la taille d'une clique maximum. Ici, on s'intéresse à une étape clé de la preuve correspondante ; comment colorer économiquement un graphe dans lequel aucun sommet ne "voit beaucoup d'arêtes" dans son voisinage ? Nous améliorons la méthode probabiliste utilisée dans ce cas, et appliquons notamment le résultat à la coloration forte d'arêtes (coloration d'arêtes telle qu'aucune arête n'est incidente à deux arêtes de même couleur). Erdos et Nesetril ont conjecturé en 1989 que tout graphe de degré maximum D admet une coloration forte d'arêtes avec 1.25 D^2 couleurs, quand la borne supérieure triviale est de 2 D^2. Notre méthode permet d'améliorer significativement la borne existante (Bruhn et Joos, 2015), ainsi que le théorème de Reed. Ces travaux sont le fruit d'une collaboration avec Thomas Perrett (Technical University of Denmark) et Luke Postle (University of Waterloo).

Vendredi 22 janvier 2016 - Roots of the chromatic polynomial, spanning trees and minors - Thomas Perrett (Technical University of Denmark).
Résumé : The real and complex roots of chromatic polynomials, which we call chromatic roots, have been studied since the 1940s yet it is not well understood how structural properties of graphs affect their chromatic roots. In this talk we survey some results and open problems, and present recent work on the following question: For a minor-closed class of graphs, what is the infimum of the non-trivial real chromatic roots of the graphs in that class?

Vendredi 29 janvier 2016 - Courte classification de quelques jeux combinatoires - Gabriela Paris.
Résumé : Le jeu de Nim est l’un des jeux combinatoires les plus populaires. Il se joue avec n tas de jetons, et à tour de rôle, deux joueurs prennent un nombre quelconque de jetons d’un des tas. Dans la version conventionnelle du jeu, le joueur à prendre le dernier jetons gagne, mais dans la version misère, celui-ci perd. Le jeu de Nim est très important dans la théorie des jeux combinatoires notamment car il introduit les nimbers, ou nombres de Grundy : à chaque position d’un jeu donné on peut lui associer un entier qui code l’ensemble d’options du jeu. Pour comprendre le jeu, il suffit de connaître ses valeurs de Grundy. Ainsi, on peut classer les jeux selon leurs particularités en version normale et en version misère. Notamment, je vais m’intéresser aux jeux de Nim et de Wythoff pour introdurie quelques classes de jeux. Je voudrais ainsi donner une classifications de certains jeux connus et exposer une nouvelle variante du jeu de Wythoff.

Vendredi 5 février 2016 - Résultats récents sur les jeux de coloration - Clément Charpentier.
Résumé : Le jeu de coloration est une version à deux joueurs du problème de coloration de graphes, où un joueur tente d'empêcher l'autre de réussir à colorier proprement le graphe. Nous présentons quelques résultats récents sur ces jeux : des résultats sur les graphes très peu denses (cactus de grandes mailles), des inégalités de type Nordhaus-Gaddum, et, si nous avons le temps, des résultats sur les 'line graphs'.

Vendredi 12 février 2016 - 1-2(-3) conjecture équilibrée - Mohammed Senhaji.
Résumé : La 1-2-3 conjecture a été introduite en 2004 par Michał Karonski, Tomasz Łuczak et Andrew Thomason. Ils y affirment que pour tout graphe sans composante isomorphe à K_2 il existe une pondération des arêtes avec les entiers 1,2,3, telle que les sommes sur chaque sommet des poids des arêtes incidentes forment une coloration propre des sommets. En 2010, Jakub Przybyło et Mariusz Wozniak conjecturent que si on permet l'attribution des poids aux sommets également, alors pour tout graphe il existe une telle pondération avec les entiers 1,2. Nous présentons une nouvelle variante de ces pondérations, où on exige qu'elles soient équitables, c.-à-d. que chaque poids soit utilisé le même nombre de fois, à une unité près. Nous exposons en particulier quelques résultats obtenus sur les arbres, les graphes bipartis et les graphes complets.

Vendredi 19 février 2016 - Vertex ranking of a graph - Ilan Karpas.
Résumé : A vertex ranking of a graph G is a coloring of its vertices, so that for every simple path P, the maximum color occurring in it is unique in P. The vertex-ranking chromatic-number of G, $\chi_{vr}(G)$, is the minimum number of colors for which G has a vertex-ranking. This notion is well documented in the literature, and has some well known practical applications. In this talk we present a relaxation of the vertex ranking notion, a k-vertex ranking. : A k-vertex ranking of a graph G is a coloring of its vertices, so that for every simple path P of length at most k, the maximum color occurring in it is unique in P. Similarly, The k-vertex-ranking chromatic-number of G, $\chi_{vr_k}(G)$, is the minimum number of colors with which G can be colored. For planar graphs and minor-free graphs, we show a bound of O(logn) on the k-vertex-ranking chromatic number for k constant. We also provide upper and lower bounds of the 2-vertex-ranking chromatic-number for the families of trees and d-degenerate graphs. We compare our bounds to the bounds already found for the case of ordinary vertex ranking.

Joint work with Ofer Neiman and Shakhar Smorodinsky.

Vendredi 4 mars 2016 - The coloring problem in graphs with structural restrictions - Lucas Pastor.
Résumé : Graph coloring is an NP-complete problem in general. Even for a fixed k >= 3 and for a fixed graph H that is not a collection of paths, deciding whether a graph with no induced copy of H is k-colorable is NP-hard. Here we consider the case where H is a path on six vertices. Whether 4-coloring graphs with no induced path on six vertices can be decided in polynomial time remains an open question. We answer positively in the restricted setting of bull-free graphs, through structural observations that lead to a polynomial algorithm. This is joint-work with Frédéric Maffray.

Vendredi 11 mars 2016 - Journée de l'école doctorale.

Vendredi 18 mars 2016 - Homomorphismes localement injectifs sur les tournois - Thomas Bellitto.
Résumé : Cet exposé présente un travail mené à l'université de Victoria (BC, Canada) avec Stephan Bard, Christopher Duffy, Gary MacGillivray et Feiran Yang. Nous étudions les homomorphismes sur les graphes orientés et ajoutons une contrainte supplémentaire d'injectivité locale pour laquelle plusieurs modèles existent. Cet exposé présente plusieurs définitions différentes et cherche à établir pour chacune la classe de complexité du problème d'existence d'un homomorphisme localement injectif vers un tournoi cible donné.

Vendredi 8 avril 2016 - Four ways to introduce strong edge-coloring - Martina Mockovčiaková.
Résumé : Strong edge-coloring is a proper edge-coloring, where every two edges at distance at most 2 are assigned distinct colors. In the talk, we introduce four different ways to define strong edge-colorings, considering other related types of edge-colorings. We focus our attention to the results regarding subcubic graphs.

Vendredi 8 avril 2016 - New proof of Seymour's theorem - Edita Rollová.
Résumé : In 1981 Seymour proved that every bridgeless graph admits a nowhere-zero 6-flow. We will provide a new proof that uses induction.

Vendredi 15 avril 2016 - Journée de l'équipe CombAlgo.

Vendredi 29 avril 2016 - Réunion BGW.

Vendredi 13 mai 2016 - Rubik's Cube: One rule to solve them all - Frédéric Mazoit.

Vendredi 27 mai 2016 - Réunion BGW.

Vendredi 10 juin 2016 - Coloration des arêtes des graphes planaires - Antonio Gallastegui.
Un grand théorème de la coloration des arêtes des graphes est le théorème de Vizing. Le théorème dit que pour tout graphe G l’indice chromatique $\chi'(G)$ de G est $\Delta(G) \le \chi'(G) \le \Delta(G)+1$. Pour tout graphe planaire avec $\Delta \ge 8$ Vizing a prouvé que $\chi'(G)(G) = \Delta$ (Class I). Cette égalité a été prouvée aussi pour $\Delta = 7$ (Sanders & Zhao) et même pour $\Delta = 5$ pour des graphes sans triangles. Partant des résultats connus $\Delta = 5, g \ge 4$, $\chi'(G)(G) = 5$ et $\Delta = 4$, $g \ge 5$, $\chi'(G)(G) = 4$ et inspirés des techniques de réductibilité et déchargement du Théorème des 4 couleurs, nous avons travaillé la réductibilité des graphes avec $\Delta = 4$, $g \ge 4$, afin d’aborder la conjecture que les graphes avec $\Delta = 4$ sans triangles sont de Class I.

Vendredi 17 juin 2016 - A Distributed Enumeration Algorithm and Applications to All Pairs Shortest Paths, Diameter - Yves Metivier.
We consider the standard message passing model; we assume the system is fully synchronous: all processes start at the same time and time proceeds in synchronised rounds. In each round each vertex can transmit a different message of size $O(1)$ to each of its neighbours. This paper proposes and analyses a distributed enumeration algorithm of vertices of a graph having a distinguished vertex which satisfies that two vertices with consecutive numbers are at distance at most $3$. We prove that its time complexity is $O(n)$ where $n$ is the number of vertices of the graph. Furthermore, the size of each message is $O(1)$ thus its bit complexity is also $O(n).$ We provide some links between this enumeration and Hamiltonian graphs from which we deduce that this enumeration is optimal in the sense that there does not exist an enumeration which satisfies that two vertices with consecutive numbers are at distance at most $2$. We deduce from this enumeration, algorithms which compute all pairs shortest paths and the diameter with a time complexity and a bit complexity equal to $O(n)$.

(travail en collaboration avec : J.M. Robson et A. Zemmari)

Vendredi 24 juin 2016 - Packing Coloring of Undirected and Oriented Generalized Theta Graphs - Daouya Laïche.
The packing chromatic number χρ(G) of an undirected (resp. oriented) graph G is the smallest integer k such that its set of vertices V (G) can be partitioned into k disjoint subsets V1, . . . , Vk, in such a way that every two distinct vertices in Vi are at distance (resp. directed distance) greater than i in G for every i, 1 ≤ i ≤ k.
We prove that the packing chromatic number of any undirected generalized theta graph lies between 3 and max{5, n3 + 2}, where n3 = |{i / 1 ≤ i ≤ p, ℓi = 3}|, and that both these bounds are tight. We then characterize undirected generalized theta graphs with packing chromatic number k for every k ≥ 3.
We also prove that the packing chromatic number of any oriented generalized theta graph lies between 2 and 5 and that both these bounds are tight.

Vendredi 1 juillet 2016 - Large regular graphs with given valency and second eigenvalue - Sebastian Cioaba.
From Alon-Boppana and Serre, we know that for any given integer $k\geq 3$ and real number $\lambda<2\sqrt{k-1}$, there are finitely many $k$-regular graphs whose second largest eigenvalue is at most $\lambda$. In this talk, I will discuss the largest number of vertices in such graphs. This is joint work with Hiroshi Nozaki (Aichi Univ. of Education, Japan), Jack Koolen (Univ. of Science and Technology of China) and Jason Vermette (Missouri Baptist Univ., USA).

Mardi 5 juillet 2016 - Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth - Valia Mitsou.
Choosability, introduced by Erdős, Rubin, and Taylor [Congr. Number. 1979], is a well-studied concept in graph theory: we say that a graph is $c$-choosable if for any assignment of a list of $c$ colors to each vertex, there is a proper coloring where each vertex uses a color from its list.

We study the complexity of deciding choosability on graphs of bounded treewidth. It follows from earlier work that 3-choosability can be decided in time $2^{2^{O(w)}}·n^{O(1)}$ on graphs of treewidth $w$. We complement this result by a matching lower bound giving evidence that double-exponential dependence on treewidth may be necessary for the problem: we show that an algorithm with running time $2^{2^{o(w)}}·n^{O(1)}$ would violate the Exponential-Time Hypothesis (ETH).

We consider also the optimization problem where the task is to delete the minimum number of vertices to make the graph 4-choosable and demonstrate that dependence on treewidth becomes triple-exponential for this problem: it can be solved in time $2^{2^{2^{O(w)}}}·n^{O(1)}$ on graphs of treewidth $w$, but an algorithm with running time $2^{2^{2^{o(w)}}}·n^{O(1)}$ would violate ETH.

The significance of the results is that these problems are apparently the first fairly natural graph-theoretic problems that require double-exponential or triple-exponential dependence on treewidth.

Joint work with Dániel Marx.

Vendredi 8 juillet 2016 - List star edge coloring of sparse graphs - Samia Kerdjoudj.
In 2008, Liu and Deng introduced an edge version of star coloring. They defined a star-edge coloring of a graph $G$ as a proper edge coloring such that every $2$-colored connected subgraph of $G$ is a path of length at most $3$. This notion is intermediate between acyclic edge coloring, when every 2-colored subgraph must be only acyclic, and strong edge coloring, when every 2-colored connected subgraph has at most two vertices. For a graph $G$, let the list star chromatic index of $G$, $ch_s'(G)$, be the minimum $k$ such that for any $k$-uniform list assignment $L$ for the set of edges, $G$ has a star edge coloring from $L$. We proved already many bounds for the list star chromatic index of subcubic sparse graphs. In this talk, we will consider graphs with any maximum degree $\Delta(G)$. No bound of the list star chromatic index is known for general graphs. In the case of sparse graphs it is possible to find bounds for the the list star chromatic index. We prove that if the maximum average degree of a graph $G$ is less than $\frac{7}{3}$ (resp., $\frac{5}{2}$,$\frac{8}{3}$), then $ch'_s(G)\leq 2\Delta(G) -1$ (resp., $ch'_s(G)\leq 2\Delta(G)$, $ch'_s(G)\leq 2\Delta(G) +1$ ).

Joint work with: André Raspaud.