JCJC SIMI 2 - JCJC : Sciences de l'information, de la matière et de l'ingénierie : Sciences de l’information, simulation

Hereditary classes of graphs – HEREDIA

Submission summary

Hereditary properties of graphs provide a general perspective to study graph properties. Several important general theorems were obtained, and the approach offers an elegant way of unifying notions and proof techniques. Further, hereditary classes of graphs play a central role in graph theory. Besides their theoretical appeal, they are also particularly relevant from an algorithmic point of view. Developing efficient algorithms for solving combinatorial problems is of great importance in optimization, operation research, computer science and more generally in all sciences concerned with efficiency. The applications include diverse areas such as transportation, telecommunication, molecular biology and industrial engineering. However, most of the graph optimization problems studied in those contexts turn out to be NP-complete for general graphs. This means that it is highly unlikely that these problems can be solved efficiently (that is, in polynomial time) on a computer. Still, it is possible that the problem considered, once restricted to the types of graphs actually arising in the real-world situation, can be solved in polynomial time. An appropriate way to formally define such types of graphs is by forbidding (in some precise sense) various kinds of substructures, so as to work in the more restricted context of hereditary classes of graphs. Not only this approach has proved to be of practical interest, but it also led to important and deep theoretical developments.

Hereditary classes of graphs defined by forbidding induced subgraphs gave rise to a plethora of research. The recent proof of the Strong Perfect Graph
Theorem, by Chudnovsky, Robertson, Seymour and Thomas, has put a focus on hereditary graph classes. The outstanding result they obtained involved
in-depth study and analysis of several hereditary graph classes. Characterizations were obtained, and the techniques led to independent results, such as the characterization of claw-free graphs and quasi-line graphs obtained by Chudnovsky and Seymour. Their structural theorem has already been applied to obtain results for combinatorial problems on (generalizations of) quasi-line graphs, for instance. Other consequences of the techniques developed by Chudnovsky et al. in the last ten years are expected. It seems particularly timely to put a lot of efforts to learn and comprehend the methods introduced, so as to extend and apply them to other combinatorial problems.

Of the utmost interest is also classes of graphs defined by forbidding minors. The general theory was mainly developed in last thirty years. Robertson and Seymour published a series of more than twenty papers, creating a whole field and proving deep results. Consequences of their work emanated in different fields, such as algorithmic theory, logic and complexity theory. We would like to work in the more general context of graphs with bounded expansion. The class of graphs with bounded expansion generalizes and unifies in a broader framework minor-closed classes of graphs, topological classes, classes of graphs with bounded degree, graphs with a linear crossing-number, and certain random graphs for instance. The notion of bounded expansion, and a further generalization called "nowhere dense graphs", correspond in a deep way to the intuitive idea of being "sparse", and were introduced by Nesetril and Ossona de Mendez in 2008. The framework thereby provided is very promising, and should allow us a better understanding of combinatorial parameters for restricted graph classes.

Project coordination

Jean-Sébastien SERENI (UNIVERSITE DE PARIS VII [DENIS DIDEROT]) – sereni@liafa.jussieu.fr

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

LIAFA (UMR 7089) UNIVERSITE DE PARIS VII [DENIS DIDEROT]

Help of the ANR 211,912 euros
Beginning and duration of the scientific project: - 48 Months

Useful links

Explorez notre base de projets financés

 

 

ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter