Induced cycles in crossing graphs of median graphs

The crossing graph G#G# of a partial cube GG has the equivalence classes of the Djoković–Winkler relation ΘΘ as vertices, two ΘΘ-classes being adjacent if they appear on some common isometric cycle. The following question [S. Klavžar, H.M. Mulder, Partial cubes and crossing graphs, SIAM J. Discrete Math. 15 (2002) 235–251, Problem 7.3] is treated: Let GG be a median graph and n≥4n≥4. Does an induced cycle CnCn in G#G# necessarily force an induced cogwheel MnMn in GG ? It is shown that the answer is positive for n=4,5n=4,5 and negative for n≥6n≥6. On the other hand it is proved that if G#G# contains an induced cycle Cn,n≥4Cn,n≥4, then GG contains some induced cogwheel MmMm, 4≤m≤n4≤m≤n. A refinement of the expansion procedure for partial cubes is obtained along the way.