首页 | 本学科首页   官方微博 | 高级检索  
     


Minimum Sum Coloring of P4-sparse graphs
Affiliation:1. L-STI,T-IDMS, University of Moulay Ismail, Faculty of Science and Technics, Errachidia, Morocco;2. L-STI,T-IDMS, University of Moulay Ismail, Faculty of Science and Technics, Errachidia, Morocco;3. L-STI,T-IDMS, University of Moulay Ismail, Faculty of Science and Technics, Errachidia, Morocco
Abstract:In this paper, we study the Minimum Sum Coloring (MSC) problem on P4-sparse graphs. In the MSC problem, we aim to assign natural numbers to vertices of a graph such that adjacent vertices get different numbers, and the sum of the numbers assigned to the vertices is minimum. First, we introduce the concept of maximal sequence associated with an optimal solution of the MSC problem of any graph. Next, based in such maximal sequences, we show that there is a large sub-family of P4-sparse graphs for which the MSC problem can be solved in polynomial-time.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号