Издательство: | Книга по требованию |
Дата выхода: | июль 2011 |
ISBN: | 978-3-8383-7367-6 |
Объём: | 112 страниц |
Масса: | 190 г |
Размеры(В x Ш x Т), см: | 23 x 16 x 1 |
This paper considers the question of whether or not a P5-free graph can be 4-colored in polynomial time. It is known that a connected P5-free graph G must have either a dominating clique or a dominating P3. Thus, when considering the 4-coloring question, we have three cases of interest: either G has a dominating K4, a dominating K3, or a dominating P3. In this paper, we demonstrate a polynomial time approach for determining whether or not a P5-free graph G with a dominating K4 can be 4-colored.
Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.