A comprehensive introduction to the theory of word-representable graphs

Sergey Kitaev

A comprehensive introduction to the theory of word-representable graphs

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

274 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 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	http://www.cant.ulg.ac.be/dlt/

Keywords

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

Access to Document

Kitaev-DLT-2017-A-comprehensive-introduction-to-the-theory-of-word-representable-graphsAccepted author manuscript, 564 KB

Cite this

@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; 21st International Conference on Developments in Language Theory, DLT 2017 ; Conference date: 07-08-2017 Through 11-08-2017",

year = "2017",

month = may,

day = "17",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer-Verlag",

booktitle = "Developments in Language Theory",

url = "http://www.cant.ulg.ac.be/dlt/",

}

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

T2 - 21st International Conference on Developments in Language Theory

Y2 - 7 August 2017 through 11 August 2017

ER -

A comprehensive introduction to the theory of word-representable graphs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this