For a fixed graph H, the H-coloring problem takes as an instance a graph G and asks whether there exists a homomorphism from G to H, i.e., a mapping f: V(G) -> V(H) such that if uv is an edge of G, then f(u)f(v) is an edge of H. Graph homomorphisms are a well-known generalization of graph colorings, one of the most popular and elegant objects in graph theory. Indeed, for any k>0, the notions of k-coloring and K_k-coloring (of G) coincide.
The H-coloring problem is polynomial-time solvable when H is bipartite or has a loop, and NP-complete otherwise. In general, the existence of algorithms solving NP-complete cases of H-coloring significantly faster than brute-force is unlikely under standard complexity assumptions. However, it is still possible to find algorithms working in time polynomial, or at least subexponential, in the size of the instance, if we put additional assumptions on the class of input instances. In this talk, I will show what can be achieved in the classes of F-free graphs, i.e., graphs defined by forbidding a fixed graph F as an induced subgraph. In particular, we examine to which extent the variety of tools developed to work on coloring and independent set problems in these graphs can be applied.
[Karolina Okrasa] (Oxford University)
[ https://www.unravel.rwth-aachen.de/cms/unravel/das-graduiertenkolleg/te… ] https://scholar.google.com/citations?user=rujf5v8AAAAJ&hl=pl
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .