Word-Representable Graphs: Orientations, Posets, and Bounds

  • Zion Hefty
  • Paul Horn
  • Colby Muir
  • Andrew Owens

Abstract

Word-representable graphs were originally introduced by Kitaev and Pyatkin, motivated by work of Kitaev and Seif in algebra. Since their introduction, however, there has been a great deal of work in understanding their graph theoretical properties. In this paper, we introduce tools from partially ordered sets, Ramsey theory as well as probabilistic methods to study them. Through these, we settle a number of open problems in the field, regarding both the existence and length of word-representations for various classes of graphs.

Published
2024-10-04
Article Number
P4.2