BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:cb93ef95-90de-4fc0-b2e9-5dccad1684eb
X-WR-CALNAME:Dimitri Lajou PhD: 'On various graph coloring problems'
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20231029T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20211031T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20221030T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20210328T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20220327T020000
RDATE:20230326T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:cb93ef95-90de-4fc0-b2e9-5dccad1684eb
DTSTAMP:20260404T121905Z
CLASS:PUBLIC
DESCRIPTION:In this thesis\, we study graph coloring problems. We are inter
 ested in two families of coloring. The first one consists in coloring grap
 hs\, called signed graphs\, modeling social relations. These graphs have t
 wo types of edges: positive edges to represent friendship and negative edg
 es to represent animosity. We can color signed graphs through the notion o
 f homomorphism: the chromatic number of a signed graph (G\, σ) is then the
  minimum number of vertices of a signed graph (H\, π) such that (G\, σ) ad
 mits a homomorphism to (H\, π). We study the complexity of signed graph ho
 momorphisms when the target is fixed and when the input can be changed\, a
 nd obtain P/NP-complete and FPT/W[1]-difficult dichotomies. We obtain uppe
 r bounds on the chromatic number of a signed graph when the graph has few 
 cycles. Finally\, we study the relations between homomorphisms of signed g
 raphs and the Cartesian product of signed graphs. The second family of col
 oring consists in coloring edges instead of vertices according to differen
 t criteria.\nWe study four types of edge coloring: packing edge coloring\,
  injective edge coloring\, AVD coloring and 1-2-3 labeling. Packing edge c
 oloring is a form of clean edge coloring where each color has its own conf
 lict rules\, e.g.\, color 1 could obey the rules of clean edge coloring wh
 ile color 2 would obey the rules of strong edge coloring. We study this fo
 rm of coloring on subcubic graphs by giving upper bounds on the number of 
 colors needed to color these graphs. An injective edge coloring is an edge
  coloring such that for each path of length 3\, the two edges at the ends 
 of the path do not have the same color.\nWe determine the complexity of in
 jective edge coloring on several classes of graphs. For AVD colorings\, i.
 e.\, proper edge colorings where adjacent vertices are incident to differe
 nt color sets\, we obtain upper bounds on the number of colors required to
  color the graph when the maximum degree of the graph is significantly lar
 ger than its maximum average degree\, or when the graph is planar and has 
 a maximum degree greater than or equal to 12. Finally\, we prove the 1-2-3
  Multiplicative Conjecture: for any connected graph (not reduced to an edg
 e)\, one can color its edges with the colors 1\, 2 and 3 in such a way tha
 t the (vertex) coloring obtained by associating to a vertex the product of
  the colors of its incident edges is clean.
DTSTART;TZID=Europe/Paris:20211210T100000
DTEND;TZID=Europe/Paris:20211210T140000
LOCATION:Amphi A\, Bât A29
ORGANIZER;CN=Hervé Hocquard:mailto:herve.hocquard@u-bordeaux.fr
SEQUENCE:0
SUMMARY:Dimitri Lajou PhD: 'On various graph coloring problems'
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
