Word-representable graphs, characterized by the existence of a semi-transitive orientation, form a well-studied class in graph theory. Comparability graphs form a subclass of word-representable graphs. Both comparability graphs and word-representable graphs are hereditary, meaning they can be characterized by their forbidden induced subgraphs. The minimal forbidden induced subgraphs of comparability graphs and word-representable graphs are referred to as minimal non-comparability graphs and minimal non-word-representable graphs, respectively. While the set of all minimal non-comparability graphs is known, a complete description of minimal non-word-representable graphs remains open. In this paper, we classify all minimal non-comparability graphs into those that are word-representable and those that are not, thereby identifying precisely which minimal non-comparability graphs are also minimal non-word-representable. This classification further allows us to describe minimal non-word-representable graphs containing an all-adjacent vertex, obtained by adding such a vertex to each word-representable minimal non-comparability graph. As a result, we identify several infinite families of minimal non-word-representable graphs, thereby advancing the structural understanding of this class.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Word-Representability of Minimal Non-comparability Graphs

  • Benny George Kenkireth,
  • Gopalan Sajith,
  • Sreyas Sasidharan

摘要

Word-representable graphs, characterized by the existence of a semi-transitive orientation, form a well-studied class in graph theory. Comparability graphs form a subclass of word-representable graphs. Both comparability graphs and word-representable graphs are hereditary, meaning they can be characterized by their forbidden induced subgraphs. The minimal forbidden induced subgraphs of comparability graphs and word-representable graphs are referred to as minimal non-comparability graphs and minimal non-word-representable graphs, respectively. While the set of all minimal non-comparability graphs is known, a complete description of minimal non-word-representable graphs remains open. In this paper, we classify all minimal non-comparability graphs into those that are word-representable and those that are not, thereby identifying precisely which minimal non-comparability graphs are also minimal non-word-representable. This classification further allows us to describe minimal non-word-representable graphs containing an all-adjacent vertex, obtained by adding such a vertex to each word-representable minimal non-comparability graph. As a result, we identify several infinite families of minimal non-word-representable graphs, thereby advancing the structural understanding of this class.