## Abstract

Letters

Word-representable graphs generalize several important classes of graphs such as circle graphs, 3-colorable graphs and comparability graphs. This paper offers a comprehensive introduction to the theory of word-representable graphs including the most recent developments in the area.

*x*and*y*alternate in a word*w*if after deleting in*w*all letters but the copies of*x*and*y*we either obtain a word*xyxy*⋯ (of even or odd length) or a word*yxyx*⋯ (of even or odd length). A graph*G=(V,E)*is word-representable if and only if there exists a word*w*over the alphabet*V*such that letters*x*and*y*alternate in*w*if and only if*xy*∈*E*.Word-representable graphs generalize several important classes of graphs such as circle graphs, 3-colorable graphs and comparability graphs. This paper offers a comprehensive introduction to the theory of word-representable graphs including the most recent developments in the area.

Original language | English |
---|---|

Title of host publication | Developments in Language Theory |

Subtitle of host publication | 21th International Conference, DLT 2017, Leige, Belgium, August 7-11, 2017, Proceedings |

Place of Publication | Berlin |

Publisher | Springer-Verlag |

Publication status | Accepted/In press - 17 May 2017 |

Event | 21st International Conference on Developments in Language Theory - University of Liège, Liege, Belgium Duration: 7 Aug 2017 → 11 Aug 2017 http://www.cant.ulg.ac.be/dlt/ |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer-Verlag |

ISSN (Print) | 0302-9743 |

### Conference

Conference | 21st International Conference on Developments in Language Theory |
---|---|

Abbreviated title | DLT 2017 |

Country/Territory | Belgium |

City | Liege |

Period | 7/08/17 → 11/08/17 |

Internet address |

## Keywords

- word-representable graphs
- pattern avoiding words
- semi-trasitive orientations
- non-word representable graphs
- operations
- edge subdivision
- edge contraction
- cartesian products
- planar graphs