Obstruction characterization of co-TT graphs

Autor:	Das, Ashok Kumar, Paul, Indrajit
Rok vydání:	2023
Předmět:	Computer Science - Discrete Mathematics Mathematics - Combinatorics
Druh dokumentu:	Working Paper
Popis:	Threshold tolerance graphs and their complement graphs ( known as co-TT graphs) were introduced by Monma, Reed and Trotter[24]. Introducing the concept of negative interval Hell et al.[19] defined signed-interval bigraphs/digraphs and have shown that they are equivalent to several seemingly different classes of bigraphs/digraphs. They have also shown that co-TT graphs are equivalent to symmetric signed-interval digraphs. In this paper we characterize signed-interval bigraphs and signed-interval graphs respectively in terms of their biadjacency matrices and adjacency matrices. Finally, based on the geometric representation of signed-interval graphs we have setteled the open problem of forbidden induced subgraph characterization of co-TT graphs posed by Monma, Reed and Trotter in the same paper. Comment: arXiv admin note: substantial text overlap with arXiv:2206.05917
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2308.12614 Zobrazit plný text záznamu View this record from Arxiv