Żak's graph-packing conjecture
Żak's graph-packing conjecture
Let and be graphs on vertices, and let and denote the edge set and maximum degree of , respectively. Two graphs pack if there is a bijection between their vertex sets that maps every edge of to a non-edge of . Żak's graph-packing conjecture. If
and
then and pack. Żak's preceding theorem proves the same sufficient condition with replaced by , so the conjecture asks for the sharp constant bound; the source provides no resolution.
Sources & referencesView supporting material
Primary source
Ervin Győri, Alexandr Kostochka, Andrew McConvey and Derrek Yager, “Toward Żak's conjecture on graph packing”, arXiv:1508.03672 (2015).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.