BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:3c61384f-004e-45d6-9416-c7ed3c43805c
X-WR-CALNAME:[gt.go] - 'The hardness of  determining the irregularity stren
 gth of graphs' by Julien Bensmail
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20251026T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20231029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20241027T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20230326T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20240331T020000
RDATE:20250330T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:3c61384f-004e-45d6-9416-c7ed3c43805c
DTSTAMP:20260418T184108Z
CLASS:PUBLIC
DESCRIPTION:/Exposé /Talk/ \n\nThe irregularity strength s(G) of a graph G 
 is the smallest k such that the edges of G can be labelled with 1\,...\,k 
 so that no two vertices are incident to the same sum of labels. This param
 eter was introduced in the late 1980s as an alternative way to deal with a
 n optimisation problem where one aims at making a graph irregular by multi
 plying its edges in an optimal way. Since then\, the irregularity strength
  has received a lot of attention\, focusing mainly on proving bounds and i
 nvestigating side aspects and variants. \n\nIn a recent work\, we consider
 ed the algorithmic complexity of determining the irregularity strength of 
 a given graph. We proved that two close variants of this problem are NP-ha
 rd\, which we suspect might indicate that the original problem is hard too
 . Namely\, we proved that determining the distant irregularity strength\, 
 where only vertices within a certain distance are required to be incident 
 to different sums of labels\, and the multiset irregularity strength\, whe
 re any two distinct vertices are required to be incident to different mult
 isets of labels\, are NP-hard problems. \n\nThe talk will essentially be f
 ocused on introducing the general problem (which remains open to date)\, o
 n going through most of the ideas behind the proofs of our two results\, a
 nd on explaining what we can get and learn from our arguments and tools. 
 \n\n\n[Julien Bensmail] (Université Côte d'Azur ) \nhttp://jbensmai.fr/ \n
 \n\nRemarks / Remarques \n\nFind all the information of the working group 
 on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?user
 lang=en | web page ] . \nRetrouvez toutes les informations du GT sur cette
  [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web 
 ] .
DTSTART;TZID=Europe/Paris:20231117T140000
DTEND;TZID=Europe/Paris:20231117T150000
LOCATION:LaBRI/178
SEQUENCE:0
SUMMARY:[gt.go] - 'The hardness of  determining the irregularity strength o
 f graphs' by Julien Bensmail
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
