Polyominos and perfect graphs (Q1322110)

The perfect graph approach to study the combinatorial structure of visibility graphs in polyominos can be traced back to a paper of Berge et al., who made a survey of results and a collection of problems related to polyominos. In more recent works, Rajeev, Motwani et al. turned their attention to the visibility graphs of regions inside a simple orthogonal polygon, and demonstrated the intimate connection between orthogonal polygon covers and perfect graphs. The interior of an orthogonal polygon drawn on a regular grid of the plane defines a set of cells (or squares) called a polyomino. The polyominos are simply connected (without holes). A rectangle of a polyomino is a subset of cells whose union is rectangular. One of the main features of perfect graphs is that colouring such graphs is a problem that can be solved in polynomial time, whereas in the general case the colouring problem is NP-complete. This fact motivates the study of the perfection of graphs. The standard graph terminology is used here. As usual in perfect graph theory, the subgraphs are those which are induced by a subset of vertices. \(H\subset G\) represents the fact that \(H\) is a subgraph of \(G\). The number of vertices of \(G\) is noted \(n\), the maximum size of a clique \(\omega\), the maximum size of a stable set \(\alpha\). A graph \(G\) is said to be perfect if for all \(H\subseteq G\), \(H\) can be colored with \(\omega(H)\) colors. A visibility graph has vertices that correspond to geometric components (such as points, segments or regions) and edges that correspond to the visibility of these components to each other. Many forms of visibility can be defined. If two squares \(a\) and \(b\) lie on the same row or column, the set of all squares between \(a\) and \(b\) is called the segment \((a,b)\). Whenever we write \([a,b]\), it implies that \(a\), \(b\) lie on the same row or column. A geodesic \([a,c,b]\) is the union of two orthogonal segments of squares \([a,c]\) and \([c,b]\). All the graphs that are considered here will have the squares of a polyomino as vertices. The row-visibility graph of a polyomino \(p\) is defined as follows: two squares \(a\) and \(b\) are said to see each other if \([a,b]\) is included in the polyomino, in this case \(ab\) is an edge of the row-visibility graph. The collision graph of a polyomino \(p\) is defined as follows: two squares \(a\) and \(b\) are said to be on a collision course if there is a geodesic \([a,c,b]\) included in \(p\), in this case \(ab\) is an edge of the collision graph. In this paper it is proved that row-visibility and collision graphs are perfect. First it is proved that row-visibility graphs are line graphs of bipartite graphs. (During a seminar Claude Berge conjectured the perfection of collision graphs.) Secondly the author proved that these graphs are weakly triangulated. And lastly he considered natural generalization of these graphs. In fact polyominos are useful for modelizing real-life problems. Many graphs can be associated with polyominos. Because some NP-problems become polynomial for the class of perfect graphs, to know whether or not these graphs are perfect is important from an algorithmic point of view. Thus mainly in this paper the author investigated the perfection of several kinds of graphs.