Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/193216
Полная запись метаданных
Поле DC | Значение | Язык |
---|---|---|
dc.contributor.author | Лубашева, Т. В. | - |
dc.contributor.author | Метельский, Ю. М. | - |
dc.date.accessioned | 2018-03-22T09:05:38Z | - |
dc.date.available | 2018-03-22T09:05:38Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | Журнал Белорусского государственного университета. Математика. Информатика = Journal of the Belarusian State University. Mathematics and Informatics . - 2017. - № 3. - С. 94-99 | ru |
dc.identifier.issn | 1561-834X | - |
dc.identifier.uri | http://elib.bsu.by/handle/123456789/193216 | - |
dc.description.abstract | Пусть 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 ). | ru |
dc.language.iso | ru | ru |
dc.publisher | Минск : БГУ | ru |
dc.rights | info:eu-repo/semantics/openAccess | en |
dc.subject | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика | ru |
dc.title | Характеризация и распознавание графов пересечений ребер 3-хроматических гиперграфов кратности не выше двух в классе расщепляемых графов | ru |
dc.title.alternative | 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 | ru |
dc.type | article | en |
Располагается в коллекциях: | 2017, №3 |
Полный текст документа:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
Journal of the Belarusian State University. Mathematics and Informatics_№3_2017-094-099.pdf | 1,76 MB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.