Loading Events

« All Events

  • This event has passed.
:

Sang-il Oum (엄상일), Survey on vertex-minors

April 21 Tuesday @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)

Speaker

Sang-il Oum (엄상일)
IBS Discrete Mathematics Group and KAIST
https://dimag.ibs.re.kr/home/sangil/

For a vertex v of a graph G, the local complementation at v is an operation to obtain a new graph denoted by G*v from G such that two distinct vertices x, y are adjacent in G*v if and only if both x, y are neighbors of v and x, y are non-adjacent, or at least one of x, y is not a neighbor of v and x, y are adjacent. A graph H is a vertex-minor of a graph G if H is obtained from G by a sequence of local complementation and vertex deletions. Interestingly vertex-minors have been used in the study of measurement-based quantum computing on graph states.

Motivated by the big success of the graph minor structure theory developed deeply by Robertson and Seymour since 1980s, we propose a similar theory for vertex-minors. This talk will illustrate similarities between graph minors and graph vertex-minors and give a survey of known theorems and open problems on vertex-minors of graphs.

Details

Date:
April 21 Tuesday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:
,

Venue

Room B232
IBS (기초과학연구원)

Organizer

Sang-il Oum (엄상일)
Website:
https://dimag.ibs.re.kr/home/sangil/