Loading Events

« All Events

  • This event has passed.

Jozef Skokan, Separating the edges of a graph by a linear number of paths

Tuesday, May 9, 2023 @ 4:30 PM - 5:30 PM KST

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

Recently, Letzter proved that any graph of order n contains a collection P of $O(n \log^*n)$ paths with the following property: for all distinct edges e and f there exists a path in P which contains e but not f. We improve this upper bound to 19n, thus answering a question of Katona and confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluhar and by Falgas-Ravry, Kittipassorn, Korandi, Letzter, and Narayanan.

Our proof is elementary and self-contained.


Tuesday, May 9, 2023
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B332
IBS (기초과학연구원) + Google Map


Hong Liu
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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
Copyright © IBS 2018. All rights reserved.