Lesson plan

Word-representable graph

In the mathematical field of graph theory, a word-representable graph is a graph that can be characterized by a word (or sequence) whose entries alternate in a prescribed way. In particular, if the vertex set of the graph is V, one should be able to choose a word w over the alphabet V such that letters a and b alternate in w if and only if the pair ab is an edge in the graph. (Letters a and b alternate in w if, after removing from w all letters but the copies of a and b, one obtains a word abab... or a word baba....) For example, the cycle graph labeled by a, b, c and d in clock-wise direction is word-representable because it can be represented by abdacdbc: the pairs ab, bc, cd and ad alternate, but the pairs ac and bd do not. The word w is G 's word-representant, and one says that that w represents G. The smallest (by the number of vertices) non-word-representable graph is the wheel graph W 5 , which is the only non-word-representable graph on 6 vertices. The definition of a word-representable graph works both in labelled and unlabelled cases since any labelling of a graph is equivalent to any other labelling. Also, the class of word-representable graphs is hereditary. Word-representable graphs generalise several important classes of graphs such as circle graphs, 3-colorable graphs and comparability graphs.…

Back to article

Article summary

In the mathematical field of graph theory, a word-representable graph is a graph that can be characterized by a word (or sequence) whose entries alternate in a prescribed way. In particular, if the vertex set of the graph is V, one should be able to choose a word w over the alphabet V such that letters a and b alternate in w if and only if the pair ab is an edge in the graph. (Letters a and b alternate in w if, after removing from w all letters but the copies of a and b, one obtains a word abab... or a word baba....) For example, the cycle graph labeled by a, b, c and d in clock-wise direction is word-representable because it can be represented by abdacdbc: the pairs ab, bc, cd and ad alternate, but the pairs ac and bd do not. The word w is G 's word-representant, and one says that that w represents G. The smallest (by the number of vertices) non-word-representable graph is the wheel graph W 5 , which is the only non-word-representable graph on 6 vertices. The definition of a word-representable graph works both in labelled and unlabelled cases since any labelling of a graph is equivalent to any other labelling. Also, the class of word-representable graphs is hereditary. Word-representable graphs generalise several important classes of graphs such as circle graphs, 3-colorable graphs and comparability graphs.…

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.