BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:0e8fc7d3-9a66-469b-aa27-21a111f5eb4b
X-WR-CALNAME:[gt.go] - 'Algorithmic Aspects of the Comparison of Phylogenet
 ic Network Homomorphisms in graphs with forbidden structures' par Karolina
  Okrasa
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20261025T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20241027T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20251026T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20240331T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20250330T020000
RDATE:20260329T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:0e8fc7d3-9a66-469b-aa27-21a111f5eb4b
DTSTAMP:20260425T150709Z
CLASS:PUBLIC
DESCRIPTION:For a fixed graph H\, the H-coloring problem takes as an instan
 ce 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. \n\nThe H-coloring problem is polynomial-time solvable wh
 en H is bipartite or has a loop\, and NP-complete otherwise. In general\, 
 the existence of algorithms solving NP-complete cases of H-coloring signif
 icantly faster than brute-force is unlikely under standard complexity assu
 mptions. However\, it is still possible to find algorithms working in time
  polynomial\, or at least subexponential\, in the size of the instance\, i
 f we put additional assumptions on the class of input instances. In this t
 alk\, 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 a
 pplied. \n\n[Karolina Okrasa] (Oxford University) \n[ https://www.unravel.
 rwth-aachen.de/cms/unravel/das-graduiertenkolleg/team/unravel-team/~loqwy/
 muluk-komal/?lidx=1&allou=1 ] https://scholar.google.com/citations?user=ru
 jf5v8AAAAJ&hl=pl \n\nVérifiez que vous êtes bien inscrits sur le site du [
 gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equip
 es/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/
 Equipes#membres ] \n\nRemarks / Remarques \n\nFind all the information of 
 the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.
 php/Groupe/GT?userlang=en | web page ] . \nRetrouvez toutes les informatio
 ns du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Gro
 upe/GT | page web ] . \n\n\n\nImport automatique depuis https://webmel.u-b
 ordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.ics par sync_icals_to_drup
 al.py pour GT-GO
DTSTART;TZID=Europe/Paris:20250221T140000
DTEND;TZID=Europe/Paris:20250221T150000
LOCATION:LaBRI/178
SEQUENCE:0
SUMMARY:[gt.go] - 'Algorithmic Aspects of the Comparison of Phylogenetic Ne
 twork Homomorphisms in graphs with forbidden structures' par Karolina Okra
 sa
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
