1 citations · 2 across the 10 of their papers we have counts for
4 papers · 1 filter
Restricted subgraphs of edge-colored graphs and applications
Benny Sudakov
A properly edge-colored graph is a graph with a coloring of its edges such that no vertex is incident to two or more edges of the same color. A subgraph is called rainbow if all it…
Approximate path decompositions of regular graphs
Richard Montgomery, Alp Müyesser, Alexey Pokrovskiy +1
We show that the edges of any -regular graph can be almost decomposed into paths of length roughly , giving an approximate solution to a problem of Kotzig from 1957. Along th…
Hamiltonicity of expanders: optimal bounds and applications
Nemanja Draganić, Richard Montgomery, David Munhá Correia +2
An -vertex graph is a -expander if for every with and there is an edge between every two disjoint sets of at least …
Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty +2
Given a -uniform hypergraph on vertices, an even cover in is a collection of hyperedges that touch each vertex an even number of times. Even covers are a generalizat…