A comprehensive introduction to the theory of word-representable graphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

101 Downloads (Pure)

Abstract

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 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 languageEnglish
Title of host publicationDevelopments in Language Theory
Subtitle of host publication21th International Conference, DLT 2017, Leige, Belgium, August 7-11, 2017, Proceedings
Place of PublicationBerlin
PublisherSpringer-Verlag
Publication statusAccepted/In press - 17 May 2017
Event21st International Conference on Developments in Language Theory - University of Liège, Liege, Belgium
Duration: 7 Aug 201711 Aug 2017
http://www.cant.ulg.ac.be/dlt/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer-Verlag
ISSN (Print)0302-9743

Conference

Conference21st International Conference on Developments in Language Theory
Abbreviated titleDLT 2017
CountryBelgium
CityLiege
Period7/08/1711/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

Fingerprint Dive into the research topics of 'A comprehensive introduction to the theory of word-representable graphs'. Together they form a unique fingerprint.

  • Cite this

    Kitaev, S. (Accepted/In press). A comprehensive introduction to the theory of word-representable graphs. In Developments in Language Theory: 21th International Conference, DLT 2017, Leige, Belgium, August 7-11, 2017, Proceedings (Lecture Notes in Computer Science). Berlin: Springer-Verlag.