A signed graph is a pair $(G,\sigma) $, where $ G $ is a graph and $\sigma: E (G)\to\{+,-\} $
is a signature which assigns to each edge of $ G $ a sign. Various notions of coloring of …

A signed bipartite (simple) graph (G, σ) is said to be C− 4-critical if it admits no
homomorphism to C− 4 (a negative 4-cycle) but each of its proper subgraphs does. To …

We study the complexity of graph modification problems with respect to homomorphism-
based colouring properties of edge-coloured graphs. A homomorphism from an edge …

The rise of digital networks has sparked a boom in the study and analysis of complex
systems. Social network analysis is a building block of the field and has become an …

A signed graph is a graph G together with an assignment sigma: E (G)->{+,-}. Graph coloring
and homomorphism are two of the central problems in graph theory, and those notions and …

In this thesis, we study some graph coloring problems. We are interested intwo families of
colorings. The first one consists in coloring graphs, called signed graphs, modeling social …

The 4-coloring problem is NP-complete for P_7 P 7-free graphs whereas the 3-coloring
problem can be solved in quasi-polynomial time on P_t P t-free graphs for any fixed t. We …

La deuxième famille de coloration consiste à colorer les arêtes au lieu des sommets en
respectant différents critères. Nous étudions quatre types de colorations d'arêtes: la …