  A circle graph is a graph in which the adjacency of vertices can be
represented as the intersection of chords of a circle. The problem of
calculating the chromatic number is known to be NP-complete, even on circle
graphs. In this paper, we propose a new integer linear programming formulation
for a coloring problem on circle graphs. We also show that the linear
relaxation problem of our formulation finds the fractional chromatic number of
a given circle graph. As a byproduct, our formulation gives a polynomial-sized
linear programming formulation for calculating the fractional chromatic number
of a circle graph. We also extend our result to a formulation for a capacitated
stowage stack minimization problem.
