Forbidden patterns of graphs 12-representable by pattern-avoiding words (Extended Abstract)

• Item type: SIG Technical Reports(1)
• 公開日: 2023-11-09
• タイトル: Forbidden patterns of graphs 12-representable by pattern-avoiding words (Extended Abstract)
• タイトル / 言語: en
• タイトル: Forbidden patterns of graphs 12-representable by pattern-avoiding words (Extended Abstract)
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: College of Information and Systems, Muroran Institute of Technology
• 著者所属(英): en
• 著者所属(英): College of Information and Systems, Muroran Institute of Technology
• 著者名: Asahi, Takaoka
• 著者名(英): Asahi, Takaoka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: A graph G = ({1, 2,..., n}, E) is 12-representable if there is a word w over {1, 2,..., n} such that two vertices i and j with i < j are adjacent if and only if every j occurs before every i in w. These graphs have been shown to be equivalent to the complements of simple-triangle graphs. This equivalence provides a characterization in terms of forbidden patterns in vertex orderings as well as a polynomial-time recognition algorithm. The class of 12-representable graphs was introduced by Jones et al. (2015) as a variant of word-representable graphs. A general research direction for word-representable graphs suggested by Kitaev and Lozin (2015) is to study graphs representable by some specific types of words. For instance, Gao, Kitaev, and Zhang (2017) and Mandelshtam (2019) investigated word-representable graphs represented by pattern-avoiding words. Following this research direction, this paper studies 12-representable graphs represented by words that avoid a pattern p. Such graphs are trivial when p is of length 2. When p = 111, 121, 231, and 321, the classes of such graphs are equivalent to well-known classes, such as trivially perfect graphs and bipartite permutation graphs. For the cases where p = 123, 132, and 211, this paper provides forbidden pattern characterizations. The full version can be found at arXiv : 2308.15904.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A graph G = ({1, 2,..., n}, E) is 12-representable if there is a word w over {1, 2,..., n} such that two vertices i and j with i < j are adjacent if and only if every j occurs before every i in w. These graphs have been shown to be equivalent to the complements of simple-triangle graphs. This equivalence provides a characterization in terms of forbidden patterns in vertex orderings as well as a polynomial-time recognition algorithm. The class of 12-representable graphs was introduced by Jones et al. (2015) as a variant of word-representable graphs. A general research direction for word-representable graphs suggested by Kitaev and Lozin (2015) is to study graphs representable by some specific types of words. For instance, Gao, Kitaev, and Zhang (2017) and Mandelshtam (2019) investigated word-representable graphs represented by pattern-avoiding words. Following this research direction, this paper studies 12-representable graphs represented by words that avoid a pattern p. Such graphs are trivial when p is of length 2. When p = 111, 121, 231, and 321, the classes of such graphs are equivalent to well-known classes, such as trivially perfect graphs and bipartite permutation graphs. For the cases where p = 123, 132, and 211, this paper provides forbidden pattern characterizations. The full version can be found at arXiv : 2308.15904.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2023-AL-195, 号 3, p. 1-8, 発行日 2023-11-09
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会