Coloring Fuzzy Circular Interval Graphs

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.