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

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.

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:, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.