Skip to main content
edited tags
Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25
Source Link
JoshuaZ
  • 7k
  • 2
  • 27
  • 59

Edge contractions of a graph but only along maximum cliques

Consider the following operation to an undirected graph: one is allowed to take any maximum clique and replace the clique with a single vertex which is attached to every single vertex which has an edge into the clique. Essentially then one is allowed to do a bunch of simultaneous edge contractions but only if they all form a maximum clique. One can then talk about what graphs can be formed from other graphs this way. Note if that a graph A can be formed from a graph B this way, then A is a minor of B, but the converse does not hold. One can think of this also as a restricted form of quotient graph but only allowed to quotient out with subgraphs which are maximum cliques. Is there a term in the literature for this graph relation?

I asked this question earlier on Math Stackexchange but did not get any answers.