Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Question: Is there a characterization of graphs that arise as intersections of a family of complete $k$-partite graphs on the same (finite) set of vertices?

It is clear that every such graph is $k$-colorable. Moreover, every $k$-colorable graph can be extended to a complete $k$-partite graph.

Maybe the answer to my question is "$k$-colorable graphs" but I somehow doubt it.

share|improve this question

1 Answer 1

up vote 4 down vote accepted
+50

For each $k$-coloring of a graph $G$, there is a complete $k$-partite graph in which $G$ embeds as a spanning subgraph. Suppose $u$ and $v$ are vertices of $G$ such that in any $k$-colouring, they are assigned different colours. Then they will be adjacent in any complete $k$-partite extension. (We could say that these vertices are "morally adjacent", but note that this depends on $k$ implicitly.)

Any uniquely $k$-colourable graph that is not complete $k$-partite is not the intersection of its $k$-partite embeddings.

For another example, consider the graph constructed as follows. Let $H$, with vertex set $\{1,2,3,4\}$, be the graph obtained from $K_4$ by deleting the edge $34$. Then in any 3-colouring the vertices $3$ and $4$ get the same colour. Extend $H$ by joining a new vertex $5$ to $4$; call the new graph $H_5$. Then in any 3-colouring, the vertices 3 and 4 get the same colour, and vertices 4 and 5 get different colours. So 3 and 5 get different colours in any 3-colouring, although they are not adjacent. It follows that the intersection of the complete 3-partite embeddings of $G$ contains the edge $35$. (The graph $H_5$ is not uniquely 3-colourable.)

I do not see any way of characterizing the graphs that contain a morally adjacent pair of vertices, but the answer to the question is not "$k$-colourable graphs".

share|improve this answer
    
Thank you. So this settles the subquestion (and proves that I am a weak counterexample-maker). Do you think that the characterization problem is tractable? –  Gejza Jenča Apr 3 '13 at 16:39
1  
@GejzaJenča: My feeling (for what it's worth) is that it would be hard to find a "good characterization", but there might nonetheless be an interesting one. –  Chris Godsil Apr 3 '13 at 17:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.