BESSY , Stéphane

In this paper, we are interested in computing the number of edge colourings and total colourings of a connected graph. We prove that the maximum number of $k$-edge-colourings of a connected $k$-regular graph on $n$ vertices is $k\cdot((k-1)!)^{n/2}$. Our proof is constructive and leads to a branching algorithm enumerating all the...

Motivated by some algorithmic considerations, we are interested in computing the number of edge colourings of a connected graph. Precisely, we prove that the maximum number of k-edge-colourings of a connected k-regular graph on n vertices is k((k-1)!)^{n/2}. Our proof is constructive and leads to a branching algorithm enumerating all the...

In this paper, we are interested in computing the number of edge colourings and total colourings of a graph. We prove that the maximum number of $k$-edge-colourings of a $k$-regular graph on $n$ vertices is $k\cdot(k-1!)^{n/2}$. Our proof is constructible and leads to a branching algorithm enumerating all the $k$-edge-colourings of a...

Ma nuch and Stacho [7] introduced the problem of designing f-tolerant routings in optical networks, i.e., routings which still satisfy the given requests even if f failures occur in the network. In this paper, we provide f-tolerant routings in complete and complete balanced bipartite optical networks, optimal according to two parameters: the...

A $k$-digraph is a digraph in which every vertex has outdegree at most $k$. A $(k\veel)$-digraph is a digraph in which a vertex has either outdegree at most $k$ or indegree at most $l$. Motivated by function theory, we study the maximum value $\Phi(k)$ (resp. $\Phi^\vee(k,l)$ of the arc-chromatic number over the $k$-digraphs (resp....

Let G=(V(G), E(G)) be a graph. A list assignment is an assignment of a set L(v) of integers to every vertex v of G. An L-colouring is an application C from V(G) into the set of integers such that C(v)L(v) for all v V(G) and C(u)C(v) if u and v are joined by an edge. A (k,k')-list assignment of a bipartite graph G with bipartition (A,B) is a...

A {\it $k$-digraph} is a digraph in which every vertex has outdegree at most $k$. A {\it $(k\vee l)$-digraph} is a digraph in which a vertex has either outdegree at most $k$ or indegree at most $l$. Motivated by function theory, we study the maximum value $\Phi (k)$ (resp. $\Phi^{\vee}(k,l)$) of the arc-chromatic number over the $k$-digraphs...

Bermond-Thomassen conjecture says that a digraph of minimum out-degree at least 2r−1, r >=1, contains at least r vertex-disjoint directed cycles. Thomassen proved that it is true when r=2, but it is still open for larger values of r, even when restricted to (regular) tournaments. In this paper, we present two proofs of this conjecture for...

The dichromatic number of a digraph is the minimum integer $k$ such that it admits a $k$-dicolouring, i.e. a partition of its vertices into $k$ acyclic subdigraphs. We say that a digraph $D$ is a super-orientation of an undirected graph $G$ if $G$ is the underlying graph of $D$. If $D$ does not contain any pair of symmetric arcs, we just say...

The support of a flow $x$ in a network is the subdigraph induced by the arcs $ij$ for which $x_{ij}>0$. We discuss a number of results on flows in networks where we put certain restrictions on structure of the support of the flow. Many of these problems are NP-hard because they generalize linkage problems for digraphs. For example deciding...

For a given 2-partition (V1, V2) of the vertices of a (di)graph G, we study properties of the spanning bipartite subdigraph BG(V1, V2) of G induced by those arcs/edges that have one end in each Vi, i ∈ {1, 2}. We determine, for all pairs of non-negative integers k1, k2, the complexity of deciding whether G has a 2-partition (V1, V2) such that...

Let k be a fixed integer. We determine the complexity of finding a p-partition (V1,. .. , Vp) of the vertex set of a given digraph such that the maximum out-degree of each of the digraphs induced by Vi, (1 ≤ i ≤ p) is at least k smaller than the maximum out-degree of D. We show that this problem is polynomial-time solvable when p ≥ 2k and N...

Let $K$ be a complete graph of order $n$. For $d\in (0,1)$, let $c$ be a $\pm 1$-edge labeling of $K$ such that there are $d{n\choose 2}$ edges with label $+1$, and let $G$ be a spanning subgraph of $K$ of maximum degree at most $\Delta$ and with $m(G)$ edges. We prove the existence of an isomorphic copy $G'$ of $G$ in $K$ such that the number...

A classical result of Erdős and Gallai determines the maximum size $m(n,\nu)$ of a graph $G$ of order $n$ and matching number $\nu n$. We show that $G$ has factorially many maximum matchings provided that its size is sufficiently close to $m(n,\nu)$.

We prove that every digraph of independence number at most 2 and arc-connectivity at least 2 has an out-branching $B+$ and an in-branching $B−$ which are arc-disjoint (we call such branchings a good pair). This is best possible in terms of the arc-connectivity as there are infinitely many strong digraphs with independence number 2 and...

We study the complexity of deciding whether a given digraph D = (V, A) admits a partition (A1, A2) of its arc set such that each of the corresponding digraphs D1 = (V, A1) and D2 = (V, A2) satisfy some given prescribed property. We mainly focus on the following 15 properties: being bipartite, being connected, being strongly connected, being...