A comprehensive introduction to the theory of word-representable graphs

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

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

Fingerprint

Graph in graph theory
Alternate
Odd
Circle Graph
If and only if
Comparability Graph
Generalise
Class

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

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.
Kitaev, Sergey. / A comprehensive introduction to the theory of word-representable graphs. Developments in Language Theory: 21th International Conference, DLT 2017, Leige, Belgium, August 7-11, 2017, Proceedings. Berlin : Springer-Verlag, 2017. (Lecture Notes in Computer Science).
@inproceedings{444085c56fde44b29a7638e39e949b20,
title = "A comprehensive introduction to the theory of word-representable graphs",
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 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.",
keywords = "word-representable graphs, pattern avoiding words, semi-trasitive orientations, non-word representable graphs, operations, edge subdivision, edge contraction, cartesian products, planar graphs",
author = "Sergey Kitaev",
note = "The final publication will be available at link.springer.com",
year = "2017",
month = "5",
day = "17",
language = "English",
series = "Lecture Notes in Computer Science",
publisher = "Springer-Verlag",
booktitle = "Developments in Language Theory",

}

Kitaev, S 2017, 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, 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.

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

Research output: Chapter in Book/Report/Conference proceedingConference 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 -

Kitaev S. 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. Berlin: Springer-Verlag. 2017. (Lecture Notes in Computer Science).