Thesis

On word-representability of Apollonian graphs and 1-11-representability of graphs

Downloadable Content

Download PDF
Creator
Rights statement
Awarding institution
  • University of Strathclyde
Date of award
  • 2026
Thesis identifier
  • T18124
Person Identifier (Local)
  • 202462346
Qualification Level
Qualification Name
Department, School or Faculty
Abstract
  • A graph G = (V,E) is word-representable if there exists a word w over the alphabet V such that two letters x and y alternate in w if and only if {x, y} ∈ E. The notion was introduced in the early 2000s by Kitaev and is now the subject of an extensive theory connecting graph theory, combinatorics on words, and order theory. A central result of Halldórsson, Kitaev, and Pyatkin states that a graph is word-representable if and only if it admits a semi-transitive orientation. While the class of word-representable graphs is rich containing all 3-colourable graphs, all comparability graphs, and all circle graphs, not every graph is word-representable, and characterising word-representable planar graphs remains a long-standing open problem. This thesis is divided into two parts. In the first part, we study the word-representability of Apollonian graphs, a classical family of maximal planar graphs constructed by recursively subdividing triangular faces. We focus on a natural subfamily encoded by sequences of the symbols m, ℓ, and r, which record whether each subdivision step is performed in the middle, left, or right triangle relative to the most recently created vertex. Working through the cases of zero, one, two, and three changes of direction, we obtain a complete classification of word-representability in terms of parity conditions on the runs of m-steps. In the representable cases, we exhibit explicit semi-transitive orientations arising from carefully chosen 4-colourings; in the non-representable cases, we identify induced subgraphs whose neighbourhoods are not comparability graphs, or which lie in a known family of forbidden subgraphs of Hauser. We then refine these results to show that within this subfamily, word-representability is in fact equivalent to being a circle graph, by constructing 2-uniform word-representations whenever the parity conditions hold. The proof is built around an extension invariant which tracks a local structure preserved by each subdivision step. In the second part, we turn to the more general notion of k-11 representability, introduced by Remmel and first developed by Cheon, Kim, Kim, Kitaev, and Pyatkin. A graph is k-11-representable if it admits a word in which two letters violate strict alternation at most k times exactly when the corresponding vertices are adjacent. Word-representable graphs are precisely the 0-11-representable graphs, and Cheon et al. proved that every graph is 2-11-representable, leaving open the case k = 1. Our main contribution to this problem, joint with Kitaev, Tang, Tao, and Zhang, is a proof that every graph on at most eight vertices is 1-11-representable, extending the previously known bound of seven vertices. We also introduce and study the multi-1-11 representation number of a graph and show that every graph on at most 24 vertices has multi-1-11-representation number at most 2. Subsequent to the publication of these results, Hefty, Horn, and Muir resolved the existence question completely by showing that every graph is 1-11-representable, in fact, permutationally so, and obtained near optimal bounds on representation length. We summarise this work and discuss the open questions it raises, which now form the natural sequel to the line of research begun in this thesis.
Advisor / supervisor
  • Kitaev, Sergey, 1975-
Resource Type
DOI
Funder

Relations

Items

Thumbnail Title Date Uploaded Visibility Actions
file details PDF of thesis T18124 2026-08-26 Public Download