Célia de Mello

Célia Picinin de Mello, in addition to being a very dear and special person, contributed significantly to the area of Computer Science. She was a professor at the Institute of Computing at the University of Campinas from 1985 until 2016. She is graduated in Mathematics from the Faculty of Philosophy, Sciences and Letters of Rio Claro (1974), received her master's degree in Mathematics from the University of Campinas in 1984, and her Ph.D. degree in Systems and Computer Engineering from the Federal University of Rio de Janeiro in 1992. She was a postdoctoral student at Consiglio Nazionale delle Ricerche, CNR, Italy (1999-2000). Her research interests mainly include topics in the field of Graph Theory. She coordinated more than ten national research projects uninterruptedly from 1996 until 2016, focusing on chromatic graph theory, modular decomposition, click operator, and algorithm complexity. She advised twelve graduate students. Her doctoral students are all professors at brazilian universities. She published more than 50 papers in national and international conferences and journals. Among her main contributions to the fields of Graph Theory and Algorithm Complexity stand out:

  • the determination of the total-chromatic number of Flower Snarks, Goldberg Snarks, Twisted Goldberg Snarks[1], split-indifference graphs[2], grids, near-ladders, k-dimensional cubes[3], and even maximum degree dually chordal graphs[4];
  • the verification of the Total Coloring Conjecture for powers of cycles with an even order[5] and for dually chordal graphs[4];
  • the determination of the chromatic index of split-indifference graphs[2], reduced indifference graphs[6], and odd maximum degree dually chordal graphs[4];
  • sufficient conditions for a join graph to be 1-factorizable and, as a consequence, the proof that the Hilton's Overfull Subgraph Conjecture holds true for several subclasses of join graphs[7];
  • a polynomial-time algorithm to solve the Graph Sandwich Problem restricted to P4-sparse graphs[8];
  • a characterization of the K-behaviour of some classes of graphs with few P4's using modular decomposition, as a consequence, polynomial-time algorithms for deciding the K-convergence or K-divergence of any graph in the class[9].
  • a proof that a cograph is K-convergent if and only if it is clique-Helly, as a consequence, a polynomial-time algorithm for deciding the K-convergence or K-divergence of any cograph[10];
  • a characterization of even and odd pairs in comparability and in P4-comparability graphs, as a consequence, simple algorithms for deciding whether a given pair of vertices is an even or odd pair in these classes of graphs[11];
  • the description of a family of minimal graphs which are clique-complete but have no universal vertices and a proof that recognizing clique-complete graphs is Co-NP-complete[12];
  • and a linear-time algorithm to recognize indifference graphs[13].

Additional details can be found in her curriculum.


[1] Campos, C. N., Simone Dantas, and Célia Picinin de Mello. "The total-chromatic number of some families of snarks." Discrete Mathematics 311.12 (2011): 984-988.

[2] Campos, Christiane Neme, et al. "The total chromatic number of split-indifference graphs." Discrete Mathematics 312.17 (2012): 2690-2693.

[3] Campos, C. N., and Célia Picinin de Mello. "The total chromatic number of some bipartite graphs." Electronic Notes in Discrete Mathematics 22 (2005): 557-561.

[4] de Figueiredo, Celina M. H., João Meidanis, and Célia Picinin de Mello. "Total-chromatic number and chromatic index of dually chordal graphs." Information processing letters 70.3 (1999): 147-152.

[5] Campos, C. N., and Célia Picinin de Mello. "A result on the total colouring of powers of cycles." Discrete Applied Mathematics 155.5 (2007): 585-597.

[6] de Figueiredo, Celina M. H., et al. "Decompositions for the edge colouring of reduced indifference graphs." Theoretical computer science 297.1-3 (2003): 145-155.

[7] De Simone, Caterina, and Célia Picinin de Mello. "Edge-colouring of join graphs." Theoretical computer science 355.3 (2006): 364-370.

[8] Dantas, Simone, et al. "The graph sandwich problem for P4-sparse graphs." Discrete Mathematics 309.11 (2009): 3664-3673.

[9] de Mello, Célia Picinin, Aurora Morgana, and Marco Liverani. "The clique operator on graphs with few P4's." Discrete applied mathematics 154.3 (2006): 485-492.

[10] Larrión, Francisco, et al. "The clique operator on cographs and serial graphs." Discrete Mathematics 282.1-3 (2004): 183-191.

[11] de Figueiredo, Celina M. H., et al. "Even and odd pairs in comparability and in P4-comparability graphs." Discrete applied mathematics 91.1-3 (1999): 293-297.

[12] Lucchesi, Cláudio Leonardo, Célia Picinin de Mello, and Jayme Luiz Szwarcfiter. "On clique-complete graphs." Discrete Mathematics 183.1-3 (1998): 247-254.

[13] de Figueiredo, Celina M. Herrera, João Meidanis, and Célia Picinin de Mello. "A linear-time algorithm for proper interval graph recognition." Information Processing Letters 56.3 (1995): 179-184.