Content deleted Content added
TakuyaMurata (talk | contribs) remove “ {{Technical|date=April 2020}}” as the new lead is more accessible (put the tag back if there is still concern, with specific indications on the issues) |
No edit summary |
||
Line 95:
*Characterise (non-)word-representable planar graphs.
*Characterise word-representable near-triangulations containing the complete graph ''K''<sub>4</sub> (such a characterisation is known for ''K''<sub>4</sub>-free planar graphs <ref name="Glen2019">[[arxiv:1605.01688|M. Glen. Colourability and word-representability of near-triangulations, Pure and Applied Mathematics, to appear, 2019.]]</ref>).
*Classify graphs with representation number 3. (See <ref name="Kit2013-3-repr">[[arxiv:1403.1616|S. Kitaev. On graphs with representation number 3, J. Autom., Lang. and Combin. 18 (2013), 97−112.]]</ref> for the state-of-the-art in this direction.)
*Is the [[line graph]] of a non-word-representable graph always non-word-representable?
*Are there any graphs on ''n'' vertices whose representation requires more than floor(''n''/2) copies of each letter?
*Is it true that out of all [[Bipartite graph|bipartite graphs]] [[Crown graph|crown graphs]] require longest word-representants (see <ref name="GKP18" />)?
*Characterise word-representable graphs in terms of (induced) forbidden subgraphs.
*Which (hard) problems on graphs can be translated to words representing them and solved on words (efficiently)?
| |||