• This event has passed.

# O-joung Kwon (권오정), Classes of intersection digraphs with good algorithmic properties

## June 8 Tuesday @ 3:00 PM - 4:00 PM KST

Zoom ID: 875 9395 3555 (relay)

### Speaker

O-joung Kwon (권오정)
Incheon National University & IBS Discrete Mathematics Group
http://ojkwon.com

An intersection digraph is a digraph where every vertex $v$ is represented by an ordered pair $(S_v, T_v)$ of sets such that there is an edge from $v$ to $w$ if and only if $S_v$ and $T_w$ intersect. An intersection digraph is reflexive if $S_v\cap T_v\neq \emptyset$ for every vertex $v$. Compared to well-known undirected intersection graphs like interval graphs and permutation graphs, not many algorithmic applications on intersection digraphs have been developed.

Motivated by the successful story on algorithmic applications of intersection graphs using a graph width parameter called mim-width, we introduce its directed analogue called `bi-mim-width’ and prove that various classes of reflexive intersection digraphs have bounded bi-mim-width. In particular, we show that as a natural extension of $H$-graphs, reflexive $H$-digraphs have linear bi-mim-width at most $12|E(H)|$, which extends a bound on the linear mim-width of $H$-graphs [On the Tractability of Optimization Problems on $H$-Graphs. Algorithmica 2020]

For applications, we introduce a novel framework of directed versions of locally checkable problems, that streamlines the definitions and the study of many problems in the literature and facilitates their common algorithmic treatment. We obtain unified polynomial-time algorithms for these problems on digraphs of bounded bi-mim-width, when a branch decomposition is given. Locally checkable problems include Kernel, Dominating Set, and Directed $H$-Homomorphism.

#### This seminar is a part of the “Round the World Relay in Combinatorics” on June 8, 2021.

http://people.maths.ox.ac.uk/scott/relay.htm

• 2:00 UTC, 11:00 KST Melbourne (Australia) Monash University
David Wood (Monash University), Universality in Minor-Closed Graph Classes
• 3:00 UTC, 12:00 KST Shanghai (China) Shanghai Center for Mathematical Sciences
Baogang Xu (Nanjing Normal University, China), On coloring of graphs of girth 2l+1 without longer odd holes
• 4:00 UTC, 13:00 KST Auckland (New Zealand) The University of Auckland
Jeroen Schillewaert (University of Auckland), Constructing highly regular expanders from hyperbolic Coxeter groups
• 5:00 UTC, 14:00 KST Sydney (Australia) Combinatorial Mathematics Society of Australasia
Gordon Royle (University of Western Australia (UWA)), Real chromatic roots of planar graphs
• 6:00 UTC, 15:00 KST Daejeon (Korea) IBS Discrete Mathematics Group
O-joung Kwon (Incheon National University and IBS Discrete Mathematics Group), Classes of intersection digraphs with good algorithmic properties
• 7:00 UTC, 16:00 KST Krakow (Poland) Jagiellonian University
Bartosz Walczak (Jagiellonian), Coloring polygon visibility graphs and their generalizations
• 8:00 UTC, 17:00 KST Glasgow (UK) University of Glasgow
Heng Guo (University of Edinburgh), A Markov chain approach towards the sampling Lovász local lemma
• 9:00 UTC, 18:00 KST London (UK) London School of Economics
Annika Heckel (LMU), How does the chromatic number of a random graph vary?
• 10:00 UTC, 19:00 KST Moscow (Russia) Moscow Institute of Physics and Technology
Noga Alon (Princeton and Tel Aviv)
• 11:00 UTC, 20:00 KST Budapest (Hungary) Hungarian Academy of Sciences + Eötvös Loránd University
László Lovász (Eotvos University, Budapest)
• 12:00 UTC, 21:00 KST Bordeaux (France) LaBRI
Carla Groenland (Utrecht University), Universal Graphs and Labelling Schemes
• 13:00 UTC, 22:00 KST New York (USA) City University of New York + Montclair State University + Hofstra University
Deepak Bal (Montclair State University)
• 14:00 UTC, 23:00 KST Prague (Czech) Czech Academy of Sciences + Czech Technical University + London School of Economics
Dhruv Mubayi (University of Illinois at Chicago), The feasible region of hypergraphs
• 15:00 UTC, 00:00 KST Brno (Czech) Masaryk University
James Davies (University of Waterloo), Colouring circle graphs and their generalisations
• 16:00 UTC, 01:00 KST Oxford (UK) University of Oxford
Jacob Fox (Stanford University), Removal lemmas
• 17:00 UTC, 02:00 KST Columbus (USA) Ohio State University
Allan Sly (Princeton University)
• 18:00 UTC, 03:00 KST Rio (Brazil) Instituto de Matemática Pura e Aplicada
Marcelo Campos (IMPA), The singularity probability of a random symmetric matrix is exponentially small
• 19:00 UTC, 04:00 KST Atlanta (USA) Georgia Institute of Technology
Jim Geelen (University of Waterloo), Homomorphisms and colouring for graphs and binary matroids
• 20:00 UTC, 05:00 KST Santiago (Chile) Universidad de Chile
David Conlon (Caltech)
• 21:00 UTC, 06:00 KST Burnaby (Canada) Simon Fraser University
Fan Chung (UCSD), Trees and forests in Green’s functions of a graph
• 22:00 UTC, 07:00 KST Victoria (Canada) University of Victoria
Andrew Suk (UCSD), Turán-type problems for point-line incidences
• 23:00 UTC, 08:00 KST Fairbanks (USA) University of Alaska
Ron Gould (Emory), Chorded cycles

## Details

Date:
June 8 Tuesday
Time:
3:00 PM - 4:00 PM KST
Event Category:
Event Tags:
,

## Venue

Zoom ID: 875 9395 3555 (relay)

## Organizer

Sang-il Oum (엄상일)
View Organizer Website
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209