Words and Graphs

verfasst von: Sergey Kitaev, Vadim Lozin

Verlag: Springer International Publishing

Buchreihe : Monographs in Theoretical Computer Science. An EATCS Series

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

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, including a chapter on hereditary classes of graphs, the authors suggest a variety of problems and directions for further research, and they discuss interrelations of words and graphs in the literature by means other than word-representability.

The book is self-contained, and is suitable for both reference and learning, with many chapters containing exercises and solutions to seleced problems. It will be valuable for researchers and graduate and advanced undergraduate students in discrete mathematics and theoretical computer science, in particular those engaged with graph theory and combinatorics, and also for specialists in algebra.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

The core of our book is the theory of word-representable graphs, a young but very promising research area lying on the boundary of graph theory and combinatorics on words. This theory is discussed in Chapters 3{5, where we provide all necessary definitions and examples, as well as a proof of every statement we make along with references to the original sources.

Sergey Kitaev, Vadim Lozin

Chapter 2. Hereditary Classes of Graphs

Abstract

The main subject of this book, the class of word-representable graphs, belongs to a wide family of graph classes known as hereditary. In this chapter, we will take a little tour through the world of hereditary classes. In particular, we will survey basic results related to this notion and will introduce various hereditary classes pertinent to word-representable graphs. We start with a formal definition.

Sergey Kitaev, Vadim Lozin

Chapter 3. What Word-Representable Graphs Are and Where They Come from

Abstract

Definition 3.0.1. For a finite word w, A(w) denotes the set of letters occurring in w.

Sergey Kitaev, Vadim Lozin

Chapter 4. Characterization of Word-Representable Graphs in Terms of Semi-transitive Orientations

Abstract

Recall that, by Theorem 3.4.3, a graph is permutationally representable if and only if it is a comparability graph. The current chapter offers, based on [74, 75], a generalization of this theorem to the case of arbitrary word-representable graphs and so-called semi-transitive orientations (see Theorem 4.1.8). These acyclic orientations, being a generalization of transitive orientations related to partial orders, provide a powerful tool for studying word-representable graphs, in particular, allowing us to reformulate word-representability problems in pure graph-theoretical terms (via certain orientations of graphs).

Sergey Kitaev, Vadim Lozin

Chapter 5. Various Results on Word-Representable Graphs

Abstract

For what follows, recall from Dffnition 3.2.3 that for a word-representable graph G, its representation number R(G) is the minimal k such that G is k-word-representable.

Sergey Kitaev, Vadim Lozin

Chapter 6. Representing Graphs via Pattern-Avoiding Words

Abstract

Chapters 3—5 study the notion of word-representable graphs. This chapter, based on [84, 90], provides a far-reaching generalization of the notion of a word-representable graph, namely that of a u-representable graph. Section 7.7 contains other ways, including another generalization, to define the notion of word-representability.

Sergey Kitaev, Vadim Lozin

Chapter 7. Open Problems and Further Research Directions

Abstract

In this chapter, we sketch a few directions of research on word-representable graphs and discuss possible approaches to handle some of the problems (see Section 7.6).

In our opinion, one of the most challenging and interesting problems that may lead to potential applications is the following question.

Sergey Kitaev, Vadim Lozin

Chapter 8. Interrelations Between Words and Graphs in the Literature

Abstract

In previous chapters we have seen several connections between graphs and words distinct from word-representable graphs, the main topic in this book. For instance, we use words to describe graphs when we need to represent them in computer memory. On the other hand, graphs can be used to represent permutations in order to reveal some of their structural properties. The literature contains many more examples of interrelations between words and graphs and we explore some of them in this chapter.

Sergey Kitaev, Vadim Lozin

Chapter 9. More on Interrelations Between Words and Graphs

Abstract

Chapter 8 gives examples of interrelations between words and graphs in the literature. In this chapter, we provide a few more such examples that include Gray codes, the snake-in-the-box problem, de Bruijn graphs and graphs of overlapping permutations, and finding independent sets in path-schemes.

Sergey Kitaev, Vadim Lozin

Backmatter

Titel: Words and Graphs
verfasst von: Sergey Kitaev
Vadim Lozin
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-25859-1
Print ISBN: 978-3-319-25857-7
DOI: https://doi.org/10.1007/978-3-319-25859-1