Najiba Sbihi

Najiba Sbihi (born 1953) is a Moroccan mathematician and operations researcher, known for her contributions to graph theory and graph algorithms.

Education and career Sbihi earned a degree from the Faculty of Sciences of Mohammed V University in Rabat, Morocco in 1973. She continued her studies in France at Joseph Fourier University in Grenoble, first in computer science in which she earned a bachelor's degree in 1975. Continuing in operations research, she earned a diplôme d'études approfondies in 1976, a doctorat de troisième cycle in 1978 under the supervision of Michel Sakarovitch, and a doctorat d'état in 1987, supervised by Jean Fonlupt. Her doctoral study also included research in Canada with Jack Edmonds at the University of Waterloo and with Václav Chvátal at McGill University.

She worked with the Moroccan National Center for Scientific and Technical Research until, in 1992, becoming a professor of industrial engineering in the Mohammadia School of Engineering in Rabat. She headed the Department of Industrial Engineering from 1995 to 1997.

Contributions Sbihi's contributions to graph theory and graph algorithms include the discovery that the maximum independent set problem can be solved in polynomial time on claw-free graphs. With Chvátal, she proved a special case of the strong perfect graph theorem, for the graphs that have no bull graph as an induced subgraph. Their work in this area introduced a type of graph decomposition that was central to the eventual proof of the full strong perfect graph theorem. She and Chvátal also devised efficient algorithms for recognizing the claw-free perfect graphs, and later she and Bruce Reed showed how to recognize the Bull-free perfect graphs.

Selected publications