# KCL2020.12

KAIST Combinatorics Lab. Workshop

It is a triannual (three-times-a-year) seminar organized by academic genealogy from Professor Dongsu Kim in * KAIST Combinatorics Laboratory*, which KCL stands for. The aim of this seminar is to bring together active combinatorialists to discuss recent and prospective advances in

*and related areas. The style of talk tends to be less formal.*

**algebraic and enumerative combinatorics**### Information

**Title**KAIST Combinatorics Lab. Workshop 2020.12 (KCL2020.12)**Date**December 29 (Tuesday), 2020**Venue**Zoom Meeting (Meeting ID. 835 3862 1953)

### Program

**December 29****09:00 - 09:25**Ice-breaking Talks**09:25 - 09:30**Opening Address**09:30 - 10:20**Lecture by Ilkyoo Choi**Title.**Flexibility of Planar Graphs**Abstract.**Oftentimes in chromatic graph theory, precoloring techniques are utilized in order to obtain the desired coloring result. For example, Thomassen's proof for 5-choosability of planar graphs actually shows that two adjacent vertices on the same face can be precolored.

In this vein, we investigate a precoloring extension problem formalized by Dvorak, Norin, and Postle named*flexibility*. Given a list assignment*L*on a graph*G*, an*L-request*is a function on a subset*S*of the vertices that indicates a preferred color in*L(v)*for each vertex*v**∈**S*.

A graph*G*is*ε**-flexible for list size k*if given a*k*-list assignment*L*and an*L*-request, there is an*L*-coloring of*G*satisfying an*ε*-fraction of the requests in*S*.

We survey known results regarding this new concept, and prove some new results regarding flexibility of planar graphs.

**10:20 - 10:40**Coffee Break**10:40 - 11:30**Lecture by Ringi Kim**Title.**On the strong clique number of a graph**Abstract.**The strong clique number of a graph is the maximum size of a set of edges of which every pair has distance at most two. As a weakening of the renowned strong edge coloring conjecture, Faudree et al. proposed the conjecture stating that every graph*G*has strong clique number at most*5/4**Δ**(G)**²*. There have been a lot of work on the conjecture, but it still remains open. The best known upper bound is*4/3**Δ**(G)**²*by Faron et al.

In this talk, we will survey the strong clique number of various graph classes and talk about recent results regarding the strong clique number.

**11****:****3****0 - 1****2****:****3****0**Lightning Talks (about 5 minutes for each)**12:30 - 13:00**Closing Remarks (and Lunch)

### Invited Speakers

Ilkyoo Choi, Hankuk University of Foreign Studies (HUFS)

Ringi Kim, Inha University

### Participants

Dongsu Kim, KAIST

Ae Ja Yee, The Pennsylvania State University

Seunghyun Seo, Kangwon National University

Heesung Shin, Inha University

Jang Soo Kim, Sungkyunkwan University

Sun-mi Yun, Sungkyunkwan University

U-keun Song, Sungkyunkwan University

Jihyeug Jang, Sungkyunkwan University

Taehyun Eom, KAIST

Sangwook Kim, Chonnam National University

Meesue Yoo, Chungbuk National University

JiSun Huh, Ajou University

### Organizer

Heesung Shin, Inha University

Seunghyun Seo, Kangwon National University

### Sponsor

National Research Foundation of Korea