Showing 2025Show all
3 papers · 1 filter
math.CO2025
Separating edges by linearly many subdivisions
George Kontogeorgiou, Matias Pavez-Signe, Maya Stein +2
We prove that for any two graphs and , the edges of can be strongly separated by a collection of linearly many subdivisions of and single edges. This confirms a conj…
math.CO2025
Isometric and induced path partitions: a new upper bound and a characterization of some extremal graphs
Irena Penev, R. B. Sandeep, D. K. Supraja +1
An \textit{isometric path} is a shortest path between two vertices. An \textit{isometric path partition} (IPP) of a graph is a set of vertex-disjoint isometric pa…
math.CO2025
Two-block paths in oriented graphs of large semidegree
Irena Penev, S Taruni, Stéphan Thomassé +2
We study the existence of oriented paths with two blocks in oriented graphs under semidegree conditions. A block of an oriented path is a maximal directed subpath. Given positive i…