Coloring Fuzzy Circular Interval Graphs |
| |
Institution: | 1. School of Computer and Information Technology, Shanxi University, Taiyuan 030006, Shanxi, China;2. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University, Taiyuan 030006, Shanxi, China |
| |
Abstract: | Computing the weighted coloring number of graphs is a classical topic in combinatorics and graph theory. Recently these problems have again attracted a lot of attention for the class of quasi-line graphs and more specifically fuzzy circular interval graphs.The problem is NP-complete for quasi-line graphs. For the subclass of fuzzy circular interval graphs however, one can compute the weighted coloring number in polynomial time using recent results of Chudnovsky and Ovetsky and of King and Reed. Whether one could actually compute an optimal weighted coloring of a fuzzy circular interval graph in polynomial time however was still open.We provide a combinatorial algorithm that computes weighted colorings and the weighted coloring number for fuzzy circular interval graphs efficiently. The algorithm reduces the problem to the case of circular interval graphs, then making use of an algorithm by Gijswijt to compute integer decompositions. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|