KCL2020.12

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 algebraic and enumerative combinatorics and related areas. The style of talk tends to be less formal.

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:30 - 12:30 Lightning Talks (about 5 minutes for each)

  • 12:30 - 13:00 Closing Remarks (and Lunch)

Organizer

• Heesung Shin, Inha University

• Seunghyun Seo, Kangwon National University

Sponsor

• National Research Foundation of Korea