H-free-complement monochromatic path-cover conjecture
H-free-complement monochromatic path-cover conjecture
Let be a graph with chromatic number , and let be an -edge-colored graph on vertices such that is not a subgraph of the complement . H-free-complement path-cover conjecture. There exists a constant such that vertex-disjoint monochromatic paths of cover at least
vertices. The conjecture extends cycle- and path-partition questions from complete graphs to graphs whose complements exclude a fixed graph; the source proves special cases but leaves the general statement open.
Sources & referencesView supporting material
Primary source
Jozsef Balogh, Janos Barat, Daniel Gerbner, Andras Gyarfas and GAbor N. Sarkozy, “Partitioning 2-edge-colored graphs by monochromatic paths and cycles”, arXiv:1509.05544 (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.