Frédéric Maffray - Publications

(Date : 8-8-2017)

 

  1. F. Maffray. Sur l'existence de noyaux dans les graphes parfaits. Thèse de 3ème cycle, Université Paris VI, France, 1984.

  2. F. Maffray. On kernels in i-triangulated graphs. Discrete Mathematics 61 (1986), 247-252.

  3. F. Maffray, H. Meyniel. On the relationship between Hadwiger and stability numbers. Discrete Mathematics 64 (1987), 39-42.

  4. C.T. Hoàng, F. Maffray. Opposition graphs are quasi-parity graphs. Graphs and Combinatorics 5 (1989), 83-85.

  5. F. Maffray. Structural Aspects of Perfect Graphs. PhD thesis, RUTCOR Dissertation #3-89, Rutgers University, New Brunswick, NJ, USA, 1989.

  6. R. Hayward, C.T. Hoàng, F. Maffray. Optimizing weakly triangulated graphs. Graphs and Combinatorics 5 (1989), 339-349. Erratum in volume 6 (1990), 33-35.

  7. P.L. Hammer, F. Maffray. Completely separable graphs. Discrete Applied Mathematics 27 (1990), 85-99 (Special Issue, Workshop in Computational Combinatorics).

  8. C. Benzaken, Y. Crama, P. Duchet, P.L. Hammer, F. Maffray. More characterizations of triangulated and cotriangulated graphs. Journal of Graph Theory 14 (1990), 413-422.

  9. P.L. Hammer, F. Maffray, M. Queyranne. Cut-threshold graphs. Discrete Applied Mathematics 30 (1991), 163-179.

  10. C.T. Hoàng, F. Maffray, M. Preissmann. New properties of perfectly orderable graphs and strongly perfect graphs. Discrete Mathematics 98 (1991), 161-174.

  11. F. Maffray. Kernels in perfect line-graphs. Journal of Combinatorial Theory, series B, 55 (1992), 1-8.

  12. C.T. Hoàng, F. Maffray. On slim graphs, even pairs and star-cutsets. Discrete Mathematics 105 (1992), 93-102.

  13. C.T. Hoàng, F. Maffray, S. Olariu, M. Preissmann. A charming class of perfectly orderable graphs. Discrete Mathematics 102 (1992), 67-74.

  14. F. Maffray. Une étude structurelle des graphes parfaits. Thèse de doctorat de l'Université Joseph Fourier, Grenoble, 1992.

  15. P.L. Hammer, F. Maffray. Preperfect graphs. Combinatorica 13 (1993), 199-208.

  16. M. Blidia, P. Duchet, F. Maffray. On kernels in perfect graphs. Combinatorica 13 (1993), 231-233.

  17. F. Maffray. Antitwins in partitionable graphs. Discrete Mathematics 112 (1993), 275-278.

  18. L.Z. Cai, F. Maffray. On the spanning k-tree problem. Discrete Applied Mathematics 44 (1993), 139-156 (Special Issue dedicated to the memory of Martin Farber).

  19. F. Maffray, M. Preissmann. Linear recognition of pseudo-split graphs. Discrete Applied Mathematics 52 (1994), 307-312.

  20. M. Blidia, P. Duchet, F. Maffray. On the orientation of Meyniel graphs. Journal of Graph Theory 18 (1994), 705-711.

  21. F. Maffray, M. Preissmann. Perfect graphs with no P5 and no K5. Graphs and Combinatorics 10 (1994), 179-184.

  22. E. Dahlhaus, P.L. Hammer, F. Maffray, S. Olariu. On domination elimination orderings and domination graphs. Lecture Notes in Computer Science 903 (Graph-Theoretic Concepts in Computer Science, 20th International Workshop, WG 94), Springer Verlag, 1994.

  23. F. Maffray, M. Preissmann. Split neighbourhood graphs and the strong perfect graph conjecture. Journal of Combinatorial Theory, series B, 63 (1995), 294-309.

  24. M. Blidia, P. Duchet, F. Maffray. Les graphes faiblement triangulés sans P5 sont C-parfaits. Maghreb Math. Rev. 5 (1996), 13-24.

  25. J. Lehel, F. Maffray, M. Preissmann. Graphs with maximum number of minimum cuts. Discrete Applied Mathematics 65 (1996), 387-407.

  26. A. Gyárfás, D. Kratsch, J. Lehel, F. Maffray. Minimal non-neighbourhood perfect graphs. Journal of Graph Theory 21 (1996), 55-66.

  27. C.T. Hoàng, S. Hougardy, F. Maffray. On the structure of perfect graphs, 5: Overlap graphs. Journal of Combinatorial Theory B, 67 (1996), 212-237.

  28. F. Maffray, O. Porto, M. Preissmann. A generalization of simplicial elimination orderings. Journal of Graph Theory, 23 (1996), 203-208.

  29. F. Maffray, M. Preissmann. On the NP-completeness of the k-colorability problem for triangle-free graphs. Discrete Mathematics 162 (1996), 313-317.

  30. H. Aït Haddadène, F. Maffray. Coloring degenerate perfect graphs. Discrete Mathematics, 163 (1997), 211-215.

  31. H. Everett, C.M.H. de Figueiredo, C. Linhares-Sales, F. Maffray, O. Porto, B. Reed. Path parity and perfection. Discrete Mathematics, 165-166 (1997), 233-252.

  32. S. Gravier, F. Maffray. Choice number of 3-colorable elementary graphs. Discrete Mathematics 165-166 (1997), 343-348.

  33. C.M.H. de Figueiredo, F. Maffray, O. Porto. On the structure of bull-free perfect graphs. Graphs and Combinatorics, Vol. 13 (1997), 31-55.

  34. C. Linhares-Sales, F. Maffray, B. Reed. On planar perfectly contractile graphs. Graphs and Combinatorics, 13 (1997), 167-187.

  35. H. Aït Haddadène, S. Gravier, F. Maffray. An algorithm for coloring some perfect graphs. Discrete Mathematics, 183 (1998), 1-16.

  36. S. Gravier, F. Maffray. Graphs whose choice number is equal to their chromatic number. Journal of Graph Theory, 27 (1998), 87-97.

  37. C. Linhares-Sales, F. Maffray. Even pairs in claw-free perfect graphs. Journal of Combinatorial Theory B, 74 (1998), 169-191.

  38. G. Bacsó, E. Boros, V. Gurvich, F. Maffray, M. Preissmann. On minimal imperfect graphs with circular symmetry. Journal of Graph Theory 29 (1998), 209-225.

  39. F. Maffray, B.A. Reed. A description of claw-free perfect graphs. Journal of Combinatorial Theory B, 75 (1999), 134-156.

  40. F. Maffray, M. Preissmann. Sequential colorings and perfect graphs. Discrete Applied Mathematics 94 (1999), 287-296.

  41. C.T. Hoàng, F. Maffray, M. Noy. A characterization of P4-indifference graphs. Journal of Graph Theory, 31 (1999), 155-162.

  42. M. Blidia, P. Duchet, H. Jacob, F. Maffray, H. Meyniel. Some operations preserving the existence of kernels. Discrete Mathematics 205 (1999), 211-216.

  43. C.M.H. de Figueiredo, F. Maffray, O. Porto. On the structure of bull-free perfect graphs, 2: The weakly chordal case. Graphs and Combinatorics 17 (2001), 435-456.

  44. C. Linhares Sales, F. Maffray, B.A. Reed. Recognizing planar strict quasi-parity graphs. Graphs and Combinatorics 17 (2001), 745-757.

  45. H. Everett, C.M.H. de Figueiredo, C. Linhares Sales, F. Maffray, O. Porto, B.A. Reed. Even pairs. In: Perfect graphs, J.L. Ramirez-Alfonsin and B.A. Reed Eds., J. Wiley (2001), 67-92.

  46. F. Maffray, M. Preissmann. A translation of Tibor Gallai's paper: Transitiv orientierbare Graphen. In: Perfect graphs, J.L. Ramirez-Alfonsin and B.A. Reed Eds., J. Wiley (2001), 25-66.

  47. S. Gravier, C.T. Hoàng, F. Maffray. Coloring the hypergraph of maximal cliques of a graph with no long path. Discrete Mathematics 272 (2003), 285-290.

  48. C. Linhares Sales, F. Maffray. Even pairs in square-free Berge graphs. Matemática Contemporânea 25 (2003), 161-176.

  49. F. Maffray. On the coloration of perfect graphs. In: Recent Advances in Algorithmic Combinatorics (Proc. 1st Brazilian School on Combinatorics and Algorithms). C. Linhares Sales and B.A. Reed Eds. Springer (CMS books in Mathematics), 2003.

  50. S. Gravier, F. Maffray, B. Mohar. On a list-coloring problem. Discrete Mathematics 268 (2003), 303-308.

  51. S. Gravier, F. Maffray. On the choice number of claw-free perfect graphs. Discrete Mathematics 276 (2004), 211-218.

  52. C.T. Hoàng, S. Hougardy, F. Maffray, N.V.R. Mahadev. On simplicial and co-simplicial vertices in graphs. Discrete Applied Mathematics 138 (2004), 117-132.

  53. S. Dantas, S. Gravier, F. Maffray. Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum. Discrete Applied Mathematics 141 (2004), 93-101.

  54. S. Gravier, F. Maffray, J. Renault, N. Trotignon. Ramsey-type results on singletons, co-singletons and monotone sequences in large collections of sets. European Journal of Combinatorics 25 (2004), 719-734.

  55. C. Linhares Sales, F. Maffray. On dart-free perfectly contractile graphs. Theoretical Computer Science 321 (2004), 171-194.

  56. C.M.H. de Figueiredo, F. Maffray. Optimizing bull-free perfect graphs. SIAM Journal on Discrete Mathematics 18 (2004), 226-240.

  57. M. Blidia, M. Chellali, F. Maffray. On average lower independence and domination numbers in graphs. Discrete Mathematics 295 (2005), 1-11.

  58. M. Chellali, A. Khelladi, F. Maffray. Exact double domination in graphs. Discussiones Mathematicae Graph Theory 25 (2005) 291-302.

  59. F. Maffray, N. Trotignon. Algorithms for perfectly contractile graphs. SIAM Journal on Discrete Mathematics 19 (2005) 553-574.

  60. F. Maffray, N. Trotignon. A class of perfectly contractile graphs. Journal of Combinatorial Theory, Series B, Volume 96 (2006), 1-19.

  61. M. Blidia, M. Chellali, F. Maffray. Extremal graphs for a new upper bound on domination parameters in graphs. Discrete Mathematics 306 (2006) 2314-2326.

  62. C.M.H. de Figueiredo, C.T. Hoàng, F. Maffray. A characterization of P4-comparability graphs. Discrete Mathematics 306 (2006) 2461-2472.

  63. M. Burlet, F. Maffray, N. Trotignon. Odd pairs of cliques. In: Graph Theory in Paris, Proc. Conf. in Memory of Claude Berge. A. Bondy, J. Fonlupt, J.-L. Fouquet, J.-C. Fournier, J.L. Ramírez-Alfonsín (Eds.), Trends in Mathematics, Birkhäuser Verlag, 2006, pp. 85-95.

  64. C.M.H. de Figueiredo, F. Maffray, C.R. Villela Maciel. Even pairs in bull-reducible graphs. In: Graph Theory in Paris, Proc. Conf. in Memory of Claude Berge. A. Bondy, J. Fonlupt, J.-L. Fouquet, J.-C. Fournier, J.L. Ramírez-Alfonsín (Eds.), Trends in Mathematics, Birkhäuser Verlag, 2006, pp. 179-195.

  65. F. Maffray, D. Rautenbach. Small step-dominating sets in trees. Discrete Mathematics 307 (2007) 1212-1215.

  66. M. Blidia, M. Chellali, F. Maffray, J. Moncel, A. Semri. Locating-domination and identifying codes in trees. Australasian Journal of Combinatorics 39 (2007), 219-232.

  67. V. Jost, B. Lévêque, F. Maffray. Precoloring extension of co-Meyniel graphs. Graphs and Combinatorics 23 (2007) 291-301.

  68. B. Lévêque, F. Maffray. Coloring bull-free perfectly contractile graphs. SIAM Journal on Discrete Mathematics 21 (2008) 999-1018.

  69. F. Maffray, N. Trotignon, K. Vuskovic. Algorithms for square-3PC(.,.)-free Berge graphs. SIAM Journal on Discrete Mathematics 22 (2008) 51-71.

  70. C. Linhares Sales, F. Maffray, B. Reed. On planar quasi-parity graphs. SIAM Journal on Discrete Mathematics 22 (2008) 329-347.

  71. M. Blidia, M. Chellali, F. Maffray. Extremal perfect graphs for a bound on the domination number. Discrete Mathematics 308 (2008) 1785-1791.

  72. B. Lévêque, F. Maffray, B. Reed, N. Trotignon. Coloring Artemis graphs. Theoretical Computer Science 410 (2009) 2234-2240.

  73. M. Blidia, F. Maffray, Z. Zemir. On b-colorings in regular graphs. Discrete Applied Mathematics 157 (2009) 1787-1793.

  74. J. Lehel, F. Maffray, M. Preissmann. Maximum directed cuts in digraphs with degree restriction. Journal of Graph Theory 61 (2009) 140-156.

  75. F. Bonomo, G. Durán, F. Maffray, J. Marenco, M. Valencia-Pabon. On the b-coloring of cographs and P4-sparse graphs. Graphs and Combinatorics 25 (2009) 153-167.

  76. F. Maffray, M. Mechebbek. On b-perfect chordal graphs. Graphs and Combinatorics 25 (2009) 365-375.

  77. B. Lévêque, F. Maffray, M. Preissmann. Characterizing path graphs by forbidden induced subgraphs. Journal of Graph Theory 62 (2009) 369-384.

  78. C.T. Hoàng, C. Linhares Sales, F. Maffray. On minimally b-imperfect graphs. Discrete Applied Mathematics 157 (2009) 3519-3530.

  79. B. Lévêque, D. Lin, F. Maffray, N. Trotignon. Detecting induced subgraphs. Discrete Applied Mathematics 157 (2009) 3540-3551.

  80. F. Maffray. Stable sets in k-colorable P5-free graphs. Information Processing Letters 109 (2009) 1235-1237.

  81. S. Khelifi, M. Blidia, M. Chellali, F. Maffray. Double domination edge removal critical graphs. Australasian Journal of Combinatorics 48 (2010) 285-299.

  82. M. Chellali, F. Maffray, K. Tablennehas. Connected domination dot-critical graphs. Contributions to Discrete Mathematics 5 (2010) 11-25.

  83. M. Blidia, M. Chellali, R. Lounes, F. Maffray. Characterizations of trees with unique minimum locating-dominating sets. Journal of Combinatorial Mathematics and Combinatorial Computing 76 (2011) 225-232.

  84. C.M.H. de Figueiredo, F. Maffray, C.R. Villela Maciel. Transitive orientations in bull-reducible graphs. Discrete Applied Mathematics 159 (2011) 561-573.

  85. M.C. Golumbic, F. Maffray, G. Morel. A characterization of chain probe graphs. Annals of Operations Research 188 (2011) 175-183.

  86. S. Dantas, C.M.H. de Figueiredo, M.C. Golumbic, S. Klein, F. Maffray. The chain graph sandwich problem. Annals of Operations Research 188 (2011) 133-139.

  87. T. Karthick, F. Maffray. A characterization of claw-free b-perfect graphs. Discrete Mathematics 312 (2012) 324-330.

  88. M. Chellali, F. Maffray. Dominator colorings in some classes of graphs. Graphs and Combinatorics 28 (2012) 97-107.

  89. M. Blidia, N. Ikhlef-Eschouf, F. Maffray. Characterization of bγ-perfect graphs. AKCE International Journal of Graphs and Combinatorics, 9 (2012) 21-29.

  90. M. Blidia, N. Ikhlef-Eschouf, F. Maffray. b-coloring of some bipartite graphs. Australasian Journal of Combinatorics 53 (2012) 67-76.

  91. A. Brandstädt, V. Giakoumakis, F. Maffray. Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences. Discrete Applied Mathematics 160 (2012) 471-478.

  92. K. Cameron,, B. Lévêque, F. Maffray. Coloring vertices of a graph or finding a Meyniel obstruction. Theoretical Computer Science 428 (2012) 10-17.

  93. F. Maffray, A. Silva. b-colouring outerplanar graphs with large girth. Discrete Mathematics 312 (2012) 1796-1803.

  94. B. Lévêque, F. Maffray, N. Trotignon. On graphs with no induced subdivision of K4. Journal of Combinatorial Theory, Series B 102 (2012) 924-947.

  95. V. Campos, A. Gyárfás, F. Havet, C. Linhares Sales, F. Maffray. New bounds on the Grundy number of products of graphs. Journal of Graph Theory 71 (2012) 78-88.

  96. C.T. Hoàng, F. Maffray, M. Mechebbek. A characterization of b-perfect graphs. Journal of Graph Theory 71 (2012) 95-122.

  97. S. Dantas, F. Maffray, A. Silva. 2k2-Partition of some classes of graphs. Discrete Applied Mathematics 160 (2012) 2662-2668.

  98. F. Maffray, G. Morel. On 3-colorable P5-free graphs. SIAM Journal on Discrete Mathematics 26 (2012) 1682-1708.

  99. M. Blidia, N. Ikhlef-Eschouf, F. Maffray. On vertex b-critical trees. Opuscula Mathematica 33 (2013) 19-28.

  100. L. Esperet, L. Lemoine, F. Maffray, G. Morel. The chromatic number of {P5, K4}-free graphs. Discrete Mathematics 313 (2013) 743-754.

  101. L. Esperet, J. van den Heuvel, F. Maffray, F. Sipma. Fire containment in planar graphs. Journal of Graph Theory 73 (2013) 267-279.

  102. F. Maffray, A. Silva. b-colouring the Cartesian product of trees and some other graphs. Discrete Applied Mathematics 161 (2013) 650-669.

  103. F. Maffray. Fast recognition of doubled graphs. Theoretical Computer Science 516 (2014) 96-100.

  104. L. Esperet, A. Gyárfás, F. Maffray. List-coloring claw-free graphs with small clique number. Graphs and Combinatorics 30 (2014) 365-375.

  105. N. Ikhlef Eschouf, M. Blidia, F. Maffray. On edge-b-critical graphs. Discrete Applied Mathematics 180 (2015) 176-180.

  106. S. Dantas, C.M.H. de Figueiredo, F. Maffray, R.B. Teixeira. The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem. Discrete Applied Mathematics 182 (2015) 15-24.

  107. A. Berry, A. Brandstädt, V. Giakoumakis, F. Maffray. Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds. Discrete Applied Mathematics 184 (2015) 50-61.

  108. J.-L. Fouquet, F. Maffray. Domination, coloring and stability in P5-reducible graphs. Discrete Applied Mathematics 184 (2015) 122-129.

  109. L. Esperet, L. Lemoine, F. Maffray. Equitable partition of graphs into induced forests. Discrete Mathematics 338 (2015) 1481-1483.

  110. F. Maffray. Graphs with no induced wheel and no induced antiwheel Applicable Analysis and Discrete Mathematics 9 (2015) 357-366.

  111. F. Maffray. Even pairs in square-free Berge graphs. Electronic Notes in Discrete Mathematics 49 (2015) 173-180.

  112. T. Karthick, F. Maffray. Weighted independent sets in classes of P6-free graphs. Discrete Applied Mathematics 209 (2016) 217-226.

  113. T. Karthick, F. Maffray. Vizing bound for the chromatic number on some graph classes. Graphs and Combinatorics 32 (2016) 1447-1460.

  114. S. Gravier, F. Maffray, L. Pastor. On the choosability of claw-free perfect graphs. Graphs and Combinatorics 32 (2016) 2393-2413.

  115. T. Karthick, F. Maffray. Maximum weight independent sets in (S113, bull)-free graphs. Lecture Notes in Computer Science (COCOON 2016, T.N. Dinh and M.T. Thai Eds.) 9797 (2016) 385-392.

  116. F. Maffray, L. Pastor. The maximum weight stable set problem in (P6, bull)-free graphs. Lecture Notes in Computer Science (WG 2016, P. Heggernes Ed.) 9941 (2016) 85-96.

  117. L. Esperet, L. Lemoine, F. Maffray. Long induced paths in graphs. European Journal of Combinatorics 62 (2017) 1-14.

  118. H.S. Dhaliwal, A.M. Hamel, C.T. Hoàng, F. Maffray, T.J.D. McConnell, S.A. Panait. On color-critical (P5, co-P5)-free graphs. Discrete Applied Mathematics 216 (2017) 142-148.

  119. T. Karthick, F. Maffray. Maximum weight independent sets in classes related to claw-free graphs. Discrete Applied Mathematics 216 (2017) 233-239.

  120. M. Chudnovsky, L. Esperet, L. Lemoine, P. Maceli, F. Maffray, I. Penev. Graphs with no induced five-vertex path or antipath. Journal of Graph Theory 84 (2017) 221-232.

  121. L. Esperet, L. Lemoine, F. Maffray. Small feedback vertex sets in planar digraphs. The Electronic Journal of Combinatorics 24(2) (2017) P2.6.

  122. F. Maffray, L. Pastor. 4-coloring (P6, bull)-free graphs. Discrete Applied Mathematics 231 (2017) 198-210.

  123. D.J. Fraser, A.M. Hamel, C.T. Hoàng, F. Maffray. A coloring algorithm for 4K1-free line graphs. Discrete Applied Mathematics 234 (2018) 76-85.
 

http://www.g-scop.inpg.fr/~maffrayf/publications.html