欢迎光临!
您现在所在的位置:首页 >> 通知公告 & 学术信息
学术信息
SEMINARS
Word-representable graphs I
时间  Datetime
2017-04-21 09:30 — 10:30 
地点  Venue
Large Conference Room
报告人  Speaker
Sergey Kitaev
单位  Affiliation
University of Strathclyde
邀请人  Host
Jun Ma
报告摘要  Abstract

Suppose that w is a word and x and y are two distinct letters in w. We say that x and y alternate in 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 there exists a word w over the alphabet V such that distinct letters x and y alternate in w if and only if (x, y) is an edge in E. For example, the 4-cycle labeled by 1, 2, 3 and 4 in clockwise direction, can be represented by the word 13243142.

Word-representable graphs generalize several classical classes of graphs, e.g. 3-colorable, comparability, subcubic and circle graphs. Some basic questions to ask about these graphs are:

- Which graphs are word-representable?

- How many graphs on n vertices are word-representable?

- What is the minimum length of a word that represents a given graph?

The lectures will be dedicated to a comprehensive introduction to the theory of word-representable graphs, the main subject of the book “Words and graphs” recently published by Springer.

Lecture 1. Word-representable graphs. The basics.

Lecture 2. Semi-transitive orientations as the main tool in the theory of word-representable graphs discovered so far.