Let $\Sigma$ be a finite alphabet, and consider the free monoid $\Sigma^\*$. Given $w, w' \in \Sigma^\*$ we say that $w$ *overlaps* $w'$ if there exist non-empty words $u, v, u'$ such that $w = uv$ and $w' = vu'$. Given a finite set of words $S$, define the overlap graph $OG(S)$ to be the simple graph with vertex set $S$ and an edge between two words in $S$ if one overlaps the other. In general this is defined as a weighted directed graph but in this case I do not care about direction or size of the overlaps.


I would like to understand better the cliques in $OG(S)$. In particular, I would like to know:


1. Given a large enough clique, can we find a large subclique with some nicer properties?
2. Is there a bound on the chromatic number $\chi(OG(S))$ in terms of the clique number $\omega(OG(S))$ and $| \Sigma |$?


These questions can be asked with some additional hypotheses on the words in $S$. In particular:


1. What if all words in $S$ are unbordered? A word $w$ is bordered if there exist words $u, v$ such that $w = uvu$ and $u \neq \epsilon$.
2. What if all words in $S$ are Lyndon words? A word $w$ is Lyndon for a given total order $\preceq$ on $\Sigma$ if it is primitive (i.e., not a positive power of another word) and smaller than all of its proper suffixes for the corresponding lexicographic order. All Lyndon words are unbordered.


All partial answers, as well as links to relevant literature, are welcome.



Cliques in overlap graphs for words
At least one of the questions admit counterexamples. Namely, let $\Sigma = \{a, b, c, d \}$, and $S = \{ ab^nc d ab^mc : n > m \}$. Then all words in $S$ are Lyndon, $OG(S)$ is triangle-free and has infinite chromatic number. I can give more details if anyone is interested.


