5 papers · 1 filter
Rings are -bounded
Sara Asensio, Ignacio García-Marco, Kolja Knauer
We prove that there is a function such that for the zero-divisor graph of any ring , if the clique number is finite. On the on…
Coloring semiminimal Cayley Graphs
Ignacio García-Marco, Kolja Knauer, Giuliamaria Menara
In 1978 Babai raised the question whether all semiminimal Cayley graphs have bounded chromatic number. In this paper we show that semiminimal Cayley graphs of abelian and generaliz…
Sensitivity and Hamming graphs
Sara Asensio, Yuval Filmus, Ignacio García-Marco +1
For any we show that the Hamming graph admits an imbalanced partition into sets, each inducing a subgraph of low maximum degree. This improves previous resul…
Sensitivity of -ary functions and low degree partitions of Hamming graphs
Sara Asensio, Ignacio García-Marco, Kolja Knauer
The study of complexity measures of Boolean functions led Nisan and Szegedy to state the sensitivity conjecture in 1994, claiming a polynomial relation between degree and sensitivi…
Coloring minimal Cayley graphs
Ignacio García-Marco, Kolja Knauer
In 1978 Babai raised the question whether all minimal Cayley graphs have bounded chromatic number; in 1994 he conjectured a negative answer. In this paper we show that any minimal…