ПОЛИНОМИАЛЬНАЯ РАЗРЕШИМОСТЬЗАДАЧИ О РАСКРАСКЕ В ОДНОМ КЛАССЕ ГРАФОВ |
| 4 | |
| 2014 |
| научная статья | 519.17 | ||
| 288-290 | задача ораскраске, наследственный класс, полиномиальный алгоритм |
| Показывается, что задача о раскраске полиномиально разрешима в классе графов Free ({ claw , bull }) . |
 |
| 1 . Lozin V.V., Malyshev D.S. Vertex coloring of graphs with few obstructions // Discrete Applied Math-ematics (submitted). 2 . Malyshev D.S. The coloring problem for classes with two small obstructions // [Электронный ресурс]. Режим доступа: http://arxiv.org/abs/1307/02778v1. 3 . Lin M.C., Szwarcfiter J.L. Characterizations and recognition of circular-arc graphs and subclasses: A survey // Discrete Mathematics. 2009. V. 309. № 18. P. 5618-5635. 4 . Bhattacharya B., Hell P., Huang J. A linear algorithm for maximum weight cliques in proper circular arc graphs // SIAM J. Discrete Mathematics. 1996. V. 9. № 2. P. 274-289. 5 . Lozin V.V., Malyshev D.S. Vertex coloring of graphs with few obstructions // Discrete Applied Mathematics (submitted). 6 . Malyshev D.S. The coloring problem for classes with two small obstructions // [Ehlektronnyj resurs]. Rezhim dostupa: http://arxiv.org/abs/1307/02778v1. 7 . Lin M.C., Szwarcfiter J.L. Characterizations and recognition of circular-arc graphs and subclasses: A survey // Discrete Mathematics. 2009. V. 309. № 18. P. 5618-5635. 8 . Bhattacharya B., Hell P., Huang J. A linear algorithm for maximum weight cliques in proper circular arc graphs // SIAM J. Discrete Mathematics. 1996. V. 9. № 2. P. 274-289. |