New results on word-representable graphs
New results on word-representable graphs
复制标题
文字表示图的新结果
DOI：
10.1016/j.dam.2014.10.024
复制
发表时间：
2013
影响因子：
1.1
通讯作者：
V. Lozin
中科院分区：
文献类型：
--
作者：
Andrew Collins;S. Kitaev;V. Lozin
一个图G=（V，E）是词可表示的，如果在字母表V上存在一个词w，使得字母x和y在w中交替当且仅当对每个x ∈ y，（x，y）∈ E。词可表示图集概括了几个重要且已得到充分研究的图族，例如圆图、可比图、3-可着色图、顶点度最多为3的图等。通过回答Halldórsson等人提出的一个开放问题。（2011），在本文中，我们证明了不是所有顶点度最多为4的图都是词可表示的。结合这一结果和一些已知的事实，我们得到n-顶点字可表示图的个数为2n 23 + o（n2）.
Abstract A graph G=(V, E) is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if (x, y)∈ E for each x≠ y. The set of word-representable graphs generalizes several important and well-studied graph families, such as circle graphs, comparability graphs, 3-colorable graphs, graphs of vertex degree at most 3, etc. By answering an open question from Halldórsson et al.(2011), in the present paper we show that not all graphs of vertex degree at most 4 are word-representable. Combining this result with some previously known facts, we derive that the number of n-vertex word-representable graphs is 2 n 2 3+ o (n 2).