Marcin Wrochna

activity

20152020

most citedPolynomial kernelization for removing induced claws and diamonds

5 citations · 9 across the 4 of their papers we have counts for

collaborators

Showing math.COShow all

3 papers · 1 filter

math.CO2020★ 4 cited

Smaller counterexamples to Hedetniemi's conjecture

Marcin Wrochna

Hedetniemi's conjecture~\cite{hedetniemi1966homomorphisms} for $c$ -colorings states that the tensor product $G \times H$ is $c$ -colorable if and only if $G$ or $H$ is $c$ -colorable…

math.CO2018

Hedetniemi's conjecture and strongly multiplicative graphs

Claude Tardif, Marcin Wrochna

A graph K is multiplicative if a homomorphism from any product G x H to K implies a homomorphism from G or from H. Hedetniemi's conjecture states that all cliques are multiplicativ…

math.CO2018

The step Sidorenko property and non-norming edge-transitive graphs

Daniel Král', Taísa Martins, Péter Pál Pach +1

Sidorenko's Conjecture asserts that every bipartite graph H has the Sidorenko property, i.e., a quasirandom graph minimizes the density of H among all graphs with the same edge den…