# 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 dierence 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 *xy* ∈ *E*(*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 defined 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 *K _{n}* 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**).