Graph coloring:
perfect graphs,
bicritical hypergraphs,
list coloring
[ Français | English ]
Graph coloring:
perfect graphs,
bicritical hypergraphs,
list coloring
Connectivity:
min cut,
max cut,
cutwidth
Absorption:
dominating sets,
kernels
The perfect graphs were
defined by Claude Berge in 1960. These graphs generalize some
classical families of graphs (triangulated, comparability, line-graphs
of bipartite, etc.) known for having "nice properties" of
coloring. Berge conjectured that a graph is perfect if and only if
itself and its complementary do not contain as an induced subgraph an
odd chordless cycle of length at least five.
This "Strong
Perfect Graph Conjecture" remains unsolved at this time, but it
has generated an important corpus of research. Moreover, the perfect
graphs form one of the rare classes of graphs for which we know how to
solve the coloring problem in polynomial time (at least in theory),
thanks to the algorithm of Grötschel, Lovász and
Schrijver, based on the ellipsoid method for linear programming due to
L. Khachiyan. This algorithm is rather impractical though, hence
researchers try to find combinatorial algorithms that are as simple
and efficient as possible.
We are interested in solving the
Strong Perfect Graph Conjecture for new classes, as well as finding
coloring algorithms for perfect graphs, these two questions being in
fact very closely intertwined. Several of us have particularly
explored the classes of perfectly orderable graphs, of perfectly
contractile graphs, and of quasi-parity graphs. See the publications
list of Myriam
Preissmann, of Frédéric
Maffray, or the doctoral dissertation of Cláudia Linhares Sales.
The hypergraphs which are bicritical with respect to the chromatic number may curiously be related to the synthesis of logical gates (monotonous logic) by means of other basic gates. The long article project of Claude Benzaken From Logical Gates Synthesis until Bicritical Clutters explains this fact.
A hypergraph H is called bicritical if, for every edge e, the hypergraph consisting of those edges of H that do not meet e has chromatic number two less than the chromatic number of H. The bicritical hypergraphs which are graphs are the object of a still unsolved famous conjecture of Lovász (1968): they should be the complete graphs!
The bicritical hypergraphs with chromatic number 2 or 3 are well known (for 3 they are exactly the self-transversal hypergraphs without isolated vertices and with more than one edge; we suspect that, for any value of the chromatic number, many of the numerous properties of self-transversal hypergraphs are maintained in bicritical hypergraphs. In view of a possible validation of the above-mentioned conjecture of Lovász, the bicritical hypergaphs could play in hypergraph theory the role played by cliques in graph theory, allowing for example to define a more general concept of perfect hypergraph.
A self-transversal hypergraph called the flying wing:
Due to the difficulty of handling hypergraphs manually, we created a software called Clutter dedicated to this task.
A graph G is called k-list-colorable if, when each vertex is preassigned a set of size k, it is possible to color the vertices of the whole graph in such a way that each vertex is colored with a color from its assigned set (and of course adjacent vertices have different colors). This is obviously a generalization of the usual concept of vertex-coloring. Likewise one can define the list chromatic number, denoted ChiL(G), as the smallest k such that G is k-list-colorable, which clearly is greater than or equal to Chi(G). Actually, even among bipartite graphs, ChiL can be arbitrarily large. These concepts were first introduced by Vizing and, independently, by Erdös, Rubin & Taylor.
The analogue of a theorem of Hajós, proved by Sylvain Gravier, shows the primary role of complete bipartite graphs, for which however it is NP-hard to determine the value of ChiL.
A second approach is to characterize the graphs for which the two invariants Chi and ChiL are equal. In particular, a famous conjecture of Vizing asserts that Chi and ChiL are equal for all line-graphs. This conjecture was proved recently by Fred Galvin for line-graphs of bipartite graphs, thereby solving a problem of Jeff Dinitz. We have proved the equality of Chi and ChiL for a few other classes. See the doctoral dissertation by Sylvain Gravier.
A cut in an n-vertex graph is a bipartition of the vertex set, viewed as the set of all edges that go from one part to the other. Given a positive weight on each edge, finding a cut with minimum weight is a classical and well-solved problem). One may also be looking for all cuts of minimum size; this is possible and leads to a representation of the graph by a "cactus" (graph whose blocks are cycles), and yields a quadratic upper bound on the number of minimum cuts. We have studied the graphs with the largest possible number of minimum cuts (see the article by Lehel, Maffray and Preissmann, ref. 24 here).
The maximum cut problem, on the other hand, is NP-complete in general, but it becomes polynomial in the case of planar graphs. It finds some applications for example to the design of circuits or in Physics (see reference 10 in Myriam Preissmann's publications list).
The cutwidth problem (to find a linear ordering of the vertices that minimizes the maximum size of ordered cuts) has important applications in the design of very large-scale integrated circuits (VLSI), but it is also NP-complete. This problem becomes polynomial for trees, and we have an algorithm for "regular" trees (see reference 23 in Myriam Preissmann's publications list).
A dominating set is a set A of vertices such that every vertex outside A has a neighbour in A. Finding a dominating set of minimal size is a difficult ("NP-complete") problem. We are interested in this problem especially in the case of grid-like graphs (see with Sylvain Gravier).
A kernel in a directed graph is a set K of pairwise non-adjacent vertices such that every vertex outside K has a successor in K. Frequently the existence of a kernel is obtained by imposing some condition on the odd circuits of the graph, as a generalization of a classical result of Richardson. There is some connection between perfect graphs and kernels, as formulated precisely in a conjecture of Berge and Duchet in 1981 (see e.g., references [1, 2, 11, 16, 20] in Frédéric Maffray's publications). A major part of this conjecture was proved recently by Endre Boros and Vladimir Gurvich in a way that exhibits a close relationship with classical results from Game Theory.
Back to our home page