### Abstract

*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.

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 | Belgium |

City | Liege |

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

Internet address |

### Fingerprint

### Keywords

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

### Cite this

*Developments in Language Theory: 21th International Conference, DLT 2017, Leige, Belgium, August 7-11, 2017, Proceedings*(Lecture Notes in Computer Science). Berlin: Springer-Verlag.

}

*Developments in Language Theory: 21th International Conference, DLT 2017, Leige, Belgium, August 7-11, 2017, Proceedings.*Lecture Notes in Computer Science, Springer-Verlag, Berlin, 21st International Conference on Developments in Language Theory, Liege, Belgium, 7/08/17.

**A comprehensive introduction to the theory of word-representable graphs.** / Kitaev, Sergey.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

TY - GEN

T1 - A comprehensive introduction to the theory of word-representable graphs

AU - Kitaev, Sergey

N1 - The final publication will be available at link.springer.com

PY - 2017/5/17

Y1 - 2017/5/17

N2 - Letters 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.

AB - Letters 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.

KW - word-representable graphs

KW - pattern avoiding words

KW - semi-trasitive orientations

KW - non-word representable graphs

KW - operations

KW - edge subdivision

KW - edge contraction

KW - cartesian products

KW - planar graphs

UR - http://www.springer.com/gp/computer-science/lncs

UR - https://link.springer.com/bookseries/558

M3 - Conference contribution book

T3 - Lecture Notes in Computer Science

BT - Developments in Language Theory

PB - Springer-Verlag

CY - Berlin

ER -