Vertex Partitioning of Crown-Free Interval Graphs

摘要

We study the problem of finding an acyclic orientation of an undirected graph G such that each path is contained in a limited number of maximal cliques of G. In general, in an acyclic oriented graph, each path is contained in more than one maximal cliques. We focus our attention on crown-free interval graphs, and show how to find an acyclic orientation of such a graph, which guarantees that each path is contained in at most four maximal cliques. The proposed technique is used to find approximated solutions for a class of related optimization problems where a solution corresponds to an acyclic orientation of graphs.