Topics

My research activities are done within the Combinatorics and Optimisation group in LaBRI and, more specifically, within the Graphs & Applications team. My recent favourite research topics are described below.

Homomorphisms of signed graphs

A signed graph [G;Σ] is a graph G together with an assignment of signs + and -􀀀 to all the edges of G where Σ is the set of negative edges. Furthermore [G;Σ1] and [G;Σ2] are considered to be equivalent if the symmetric di erence of Σ1 and Σ2 is an edge cut of G. A signed graph [G;Σ] admits a homomorphism to [H;Σ1] if there is an equivalent signed graph [G;Σ0] of [G;Σ] and a mapping φ : V(G) → V(H) such that (i) if xyE(G) then φ(x)φ(y) ∈ E(H) and (ii) xy ∈ Σ0 if and only if φ(x)φ(y) ∈ Σ1. The chromatic number of a signed graph [G;Σ] can then be defi ned as the smallest order of a homomorphic image of [G;Σ].

Homomorphisms of oriented graphs and oriented coloring

A proper k-coloring of an undirected graph G may be viewed as a homomorphism from G to the complete graph Kn of order n. By considering now oriented graphs (that is antisymmetric digraphs), we get a new notion of coloring: an oriented k-coloring of an oriented graph G maps every vertex of G to a color from the set {1,2,…,k} in such a way that (i) adjacent vertices are assigned distinct colors and (ii) if xy and zt are two arcs in G with c(x) = c(t), then c(y) ≠ c(z) (in other words, the orientation of any arc can be deduced from the colors of its end-vertices). The oriented chromatic number of G is then defined as the smallest number of colors required for such a coloring. If G is an undirected graph, its oriented chromatic number is defined as the greatest value of the oriented chromatic number of its orientations.
A particularly challenging question in this context is to determine the oriented chromatic number of the class of planar graphs, known to lie between 18 and 80… (see The Oriented Coloring Page)

Arc-coloring of oriented graphs

As in the usual undirected case, an arc-coloring of an oriented graph G can be defined as an oriented (vertex-) coloring of its line digraph. Such an arc-coloring thus assigns colors to the arcs of G in such a way that (i) every two consecutive arcs xy and yz are assigned distinct colors and (ii) if xy and vw are two arcs with the same colors, then every two arcs of the form yz and uv are assigned distinct colors. The smallest number of colors required for such a coloring is called the oriented chromatic index of G.

Acyclic coloring

A proper coloring of an undirected graph G is acyclic if every cycle in G uses at least three colors. In other words, for any two distinct colors a and b, the subgraph of G induced by elements with color a or b is a forest. This property can be studied both for vertex and edge colorings. The corresponding parameter is respectively called acyclic chromatic number or acyclic chromatic index.

Improper acyclic coloring

An improper (vertex-) coloring of an undirected graph G allows to assign identical colors to neighboring vertices, according to some conditions concerning induced monochromatic subgraphs (subgraphs induced by vertices of any given color). Such a coloring is acyclic if for any two distinct colors a and b, the subgraph of G induced by the edges having one end-vertex colored with a and one end-vertex coloured with b is a forest. In other words, no cycle in G is an “alternating” bicolored cycle.

Incidence coloring

An incidence of an undirected graph G is a pair (v,e) where v is a vertex of G and e an edge of G incident with v. Two incidences (v,e) and (w,f) are adjacent if (i) v = w, (ii) e = f or (iii) vw = e or f. An incidence coloring of G then assigns a color to each incidence of G in such a way that adjacent incidences get distinct colors. The smallest number of colors required for such a coloring is called the incidence chromatic number of G.
Let now G be an undirected graph and G* be the digraph obtained from G by replacing each edge of G by two opposite arcs. An incidence (v,e) of G, with e = vw, can then be associated with the arc vw in G*. Therefore, an incidence coloring of G can be viewed as an arc-coloring of G* satisfying (i) any two arcs having the same source vertex (of the form uv and uw) are assigned distinct colors and (ii) any two consecutive arcs (of the form uv and vw) are assigned distinct colors. Hence, for every color c, the subgraph of G* induced by the c-colored arcs is a forest of directed stars (whose arcs are directed towards the center). The incidence chromatic number of G therefore corresponds to the directed star-arboricity of G*. (see The Incidence Coloring Page)

Coloring games

Oriented game chromatic number.

Let G be an oriented graph and C a set of k colors. Two players, say Alice and Bob, alternately choose a vertex x in G and assign to x a color in C in such a way that (i) the partial induced coloring satisfies the constraints of an oriented coloring and (ii) if xy and yz (resp. zy and yx) are two arcs in G, then the color assigned to x must be distinct from the color of z (provided z has already been colored). We then say that Alice wins the game if and only if the graph G is eventually totally colored (the aim of Bob is thus to prevent her from doing so). The oriented game chromatic number of G is then defined as the smallest k for which Alice has a winning strategy in this game.

Combinatorial coloring games.

Let us consider the following combinatorial game. Let G be an undirected graph, C a set of k colors and Alice and Bob our favourite players. Alternately, each player chooses an uncolored vertex in G and colors it in such a way that the so-obtained partial coloring is proper. The first player unable to move loses the game (normal play rule).
When k = 1, every move consists in deleting a vertex together with its neighbors and the game ends when the graph becomes empty. If, moreover, the starting graph G is a path, this game corresponds to the well-known Node-Kayles combinatorial game (octal game 0.137).