Raziskovalni matematični seminar - Arhiv
Chordal and dually chordal graphs are well known classes, whose duality becomes evident by the use of trees: a dually chordal graph is characterized by the existence of a tree such that every clique of the graph induces a subtreee (the compatible tree), whereas a chordal graph is characterized by the existence of a tree such that each member of the dual of the clique family induces a subtree (the clique tree).
For a perfect graph G, and given a weight function w on the vertices of G, linear programming duality ensures that the weight of a minimum weighted clique cover (an assignment of a non-negative weight y_C to each clique C of G, such that, each vertex v is covered by cliques whose weight sums at least w(v) and that
minimizes the total sum of the weights of the cliques) is the same as the weight of a maximum weighted stable set (a set of pairwise nonadjacent vertices S that maximizes the sum of the weights). Moreover Grötschel, Lovász and Schrijver gave in 1988 a (non combinatorial) algorithm, building upon Lovász's theta function, to compute both solutions. It is a major open problem in combinatorial optimization whether there exist polynomial time combinatorial algorithms for those two problems. For particular classes of perfect graphs, such algorithms exist. This is the case, for instance, for claw-free perfect graphs (a graph is claw-free if none of its vertices has a stable set of size three in its neighborhood).
The reconfiguration graph of the $k$-colourings of a graph $G$ contains as its vertex set the proper vertex $k$-colourings of $G$, and two colourings are joined by an edge in the reconfiguration graph if they differ in colour on just one vertex of $G$. We investigate the structure of reconfiguration graphs and the computational complexity of recognizing whether or not a pair of colourings belong to the same component of the reconfiguration graph (that is, the complexity of deciding if it is possible to transform one colouring into another with a sequence of ''recolouring'' steps that each change the colour on just one vertex without ever breaking the constraint that neighbours are not coloured alike).