Logo BSU

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ: https://elib.bsu.by/handle/123456789/193216
Заглавие документа: Характеризация и распознавание графов пересечений ребер 3-хроматических гиперграфов кратности не выше двух в классе расщепляемых графов
Другое заглавие: Characterization and recognition of edge intersection graphs of 3-chromatic hypergraphs with multiplicity at most than two in the class of split graphs / T. V. Lubasheva, Y. M. Metelsky
Авторы: Лубашева, Т. В.
Метельский, Ю. М.
Тема: ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика
Дата публикации: 2017
Издатель: Минск : БГУ
Библиографическое описание источника: Журнал Белорусского государственного университета. Математика. Информатика = Journal of the Belarusian State University. Mathematics and Informatics . - 2017. - № 3. - С. 94-99
Аннотация: Пусть Lm (k) обозначает класс графов пересечений ребер k-хроматических гиперграфов кратности не выше m. Известно, что задача распознавания графов из L1 (k) полиномиально разрешима при k = 2 и является NP-полной при k = 3. Также известно, что для любого k ≥ 2 графы из L1 (k) характеризуются конечным списком запрещенных порожденных подграфов в классе расщепляемых графов. Вопрос о сложности распознавания графов из Lm (k) при фиксированных k ≥ 2 и m ≥ 2 в настоящее время остается открытым. Здесь доказано, что для графов из L2 (3) существует конечная характеризация в терминах запрещенных порожденных подграфов в классе расщепляемых графов. Отсюда, в частности, вытекает полиномиальная разрешимость задачи распознавания G ∈ L2 (3)в классе расщепляемых графов. Результаты получены на основе доказанной в работе характеризации графов из L2 (3) в терминах степеней вершин в одном из подклассов расщепляемых графов. В свою очередь, указанная характеризация получена с помощью известного описания графов из Lm (k) в терминах покрытий кликами, а также доказанной в работе леммы о большой клике, уточняющей взаимное расположение клик в графе из Lm (k). = Let Lm (k) denote the class of edge intersection graphs of k-chromatic hypergraphs with multiplicity at most m. It is known that the problem of recognizing graphs from L 1 (k ) is polynomially solvable if k = 2 and is NP-complete if k = 3. It is also known that for any k ≥ 2 the graphs from L 1 (k ) can be characterized by a finite list of forbidden induced subgraphs in the class of split graphs. The question of the complexity of recognizing graphs from L m (k ) for fixed k ≥ 2 and m ≥ 2 remains open. Here it is proved that there exists a finite characterization in terms of forbidden induced subgraphs for the graphs from L2 (3 ) in the class of split graphs. In particular, it follows that the problem of recognizing graphs from L2 (3 ) is polynomially solvable in the class of split graphs. The results are obtained on the basis of proven here characterization of the graphs from L2 (3 ) in terms of vertex degrees in one of the subclasses of split graphs. In turn, this characterization is obtained using the well-known description of graphs from Lm (k) by means of clique coverings and proven here Lemma on large clique, specifying the mutual location of cliques in the graph from L m (k ).
URI документа: http://elib.bsu.by/handle/123456789/193216
ISSN: 1561-834X
Лицензия: info:eu-repo/semantics/openAccess
Располагается в коллекциях:2017, №3

Полный текст документа:
Файл Описание РазмерФормат 
Journal of the Belarusian State University. Mathematics and Informatics_№3_2017-094-099.pdf1,76 MBAdobe PDFОткрыть
Показать полное описание документа Статистика Google Scholar



Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.