Parikh Word Representability of Bipartite Permutation Graphs

Autor:	Teh, Wen Chean, Ng, Zhen Chuan, Javaid, Muhammad, Chern, Zi Jing
Rok vydání:	2018
Předmět:	Mathematics - Combinatorics 68R15 05C75 68R10
Druh dokumentu:	Working Paper
Popis:	The class of Parikh word representable graphs were recently introduced. In this work, we further develop its general theory beyond the binary alphabet. Our main result shows that this class is equivalent to the class of bipartite permutation graphs. Furthermore, we study certain graph theoretic properties of these graphs in terms of the arity of the representing word. Comment: Preprint, 20 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1812.10251 Zobrazit plný text záznamu View this record from Arxiv