7 papers
Small -kernels in digraphs
Irena Penev, Maya Stein, Ana Trujillo-Negrete
We address three questions of Spiro [Europ. J. Combin., 133:Paper No. 104307, 2026] on smallest -kernels in digraphs. All three questions are on the existence of small -kerne…
Star Coloring on Some Subclasses of Chordal Graphs
Germán BenÃtez-Bobadilla, Fernando Esteban Contreras-Mendoza, César Hernández-Cruz +2
A star coloring of a graph is a proper coloring in which no path on four vertices is bicolored. The star chromatic number is the minimum number of colors in a s…
Rainbow Separating Path Systems
Alexander Clifton, George Kontogeorgiou, S Taruni +1
We introduce a colorful version of separating path systems, in which two edges can only be separated from each other by two paths of distinct colors. We calculate the minimum sizes…
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…
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…
Oriented Trees in Digraphs without Oriented -cycles
Maya Stein, Ana Trujillo-Negrete
We prove that if is a digraph of maximum outdegree and indegree at least , and minimum semidegree at least that contains no oriented -cycles, then contains each…