Words and Graphs

• Main Authors: Kitaev, Sergey (Author), Lozin, Vadim (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: Cham : Springer International Publishing : Imprint: Springer, 2015.
• Edition: 1st ed. 2015.
• Series: Monographs in Theoretical Computer Science. An EATCS Series,
• Subjects: Computer science.; Computers.; Computer science > Mathematics.; Algebra.; Computer Science.; Theory of Computation.; Mathematics of Computing.

This is the first comprehensive introduction to the theory of word-representable graphs, a generalization of several classical classes of graphs, and a new topic in discrete mathematics. After extensive introductory chapters that explain the context and consolidate the state of the art in this field...

Table of Contents:

• Introduction
• Hereditary Classes of Graphs
• What Word-Representable Graphs Are and Where They Come From
• Characterization of Word-Representable Graphs in Terms of Semi-transitive Orientations
• Various Results on Word-Representable Graphs
• Open Problems and Further Research Directions on Word-Representable Graphs
• Interrelations Between Words and Graphs in the Literature
• More on Interrelations Between Words and Graphs in the Literature
• App. A: Graph Theory Background
• App. B: Beyond Graph Theory Background.