ICE-TCS Lectures Series - Magnús M. Halldórsson - Word-representable graphs
The third ICE-TCS talk for this semester will be delivered on Friday, 12 February by Magnús M. Halldórsson (Reykjavík University). The talk, which is entitled Word-representable graphs, will be held at 14:00 in room M1.05 at the new premises of Reykjavik University in Nauthólsvík.
Abstract
A graph G=(V,E) is said to be representable if there exists a word over the alphabet V such that u and v are adjacent if and only if all occurrences of u and v in the word alternate.
We give an alternative representation of these graphs as those that can be oriented to satisfy a certain semi-transitivity property. This allows us to characterize the types of graphs that are representable, in particular showing that they include 3-colorable graphs.
We also obtain bounds on the size of the word-representation, in that n occurrences of each letter suffice to represent any representable graph, while n/2 may be necessary. It follows that deciding if a graph is representable is in NP, whereas it is still open if it is in P.
This is joint work with Artem Pyatkin (Sobolev Institute of Mathematics) and Sergey Kitaev (Reykjavik University).
