Julien Bensmail

Assistant professor @ Université Côte d'Azur:

  • Research @ I3S/INRIA, joint-project COATI;
  • Teaching @ IUT Nice Côte d'Azur, département QLIO.

  • Contact information:

    • I3S/INRIA, joint-project COATI.
    • 2004, route des Lucioles, F-06902 Sophia-Antipolis, France.
    • Email: jbensmail @ unice . fr.

  • Research:

    My research activities focus on several colouring/decomposition/partition problems of graph theory, in particular on the associated structural and algorithmic aspects.
    Jxx's below are journal publications. Cxx's are conference contributions. Sxx's are submitted articles. Note that some of the Jxx's, Cxx's and Sxx's might overlap. Txx's are thesis manuscripts.
    Some of these works were presented during events; slides are gathered on this page.

    1. J68. J. Araujo, J. Bensmail, V. Campos, F. Havet, A. Karolinna Maia, N. Nisse, A. Silva. On finding the best and worst orientations for the metric dimension. Algorithmica, accepted (w/ minor revisions).
    2. J67. J. Bensmail, F. Fioravantes, F. Mc Inerney, N. Nisse, N. Oijid. The Maker-Breaker Largest Connected Subgraph Game. Theoretical Computer Science, accepted (w/ minor revisions).
    3. J66. J. Bensmail, H. Hocquard, D. Lajou, É. Sopena. A proof of the Multiplicative 1-2-3 Conjecture. Combinatorica, to appear.
    4. J65. J. Bensmail, F. Fioravantes. On proper 2-labellings distinguishing by sums, multisets or products. Discussiones Mathematicae Graph Theory, in press.
    5. J64. J. Bensmail. A σ3 condition for arbitrarily partitionable graphs. Discussiones Mathematicae Graph Theory, in press.
    6. J63. J. Bensmail. On a graph labelling conjecture involving coloured labels. Discussiones Mathematicae Graph Theory, in press.

    7. J62. J. Bensmail, H. Hocquard, D. Lajou. On the algorithmic complexity of determining the AVD and NSD chromatic indices of graphs. Theoretical Computer Science, 939:105-118, 2023.
    8. J61. J. Bensmail, F. Mc Inerney, N. Nisse. Metric Dimension: from Graphs to Oriented Graphs. Discrete Applied Mathematics, 323:28-42, 2022.
    9. J60. J. Bensmail. On the hardness of determining the irregularity strength of graphs. Theoretical Computer Science, 937:96-107, 2022.
    10. J59. J. Bensmail, F. Fioravantes, F. Mc Inerney, N. Nisse. The Largest Connected Subgraph Game. Algorithmica, 84:2533–2555, 2022.
    11. J58. J. Bensmail, B. Li. More Aspects of Arbitrarily Partitionable Graphs. Discussiones Mathematicae Graph Theory, 42(4):1237-1261, 2022.
    12. J57. J. Bensmail, H. Hocquard, P.-M. Marcille. Going Wide with the 1-2-3 Conjecture. Discrete Applied Mathematics, 320:15-32, 2022.
    13. J56. J. Bensmail, F. Dross, N. Oijid, É. Sopena. Generalising the achromatic number to Zaslavsky's colourings of signed graphs. Theoretical Computer Science, 923:196-221, 2022.
    14. J55. J. Bensmail, F. Mc Inerney. On a Vertex-Capturing Game. Theoretical Computer Science, 923:27-46, 2022.
    15. J54. J. Bensmail, H. Hocquard, D. Lajou, É. Sopena. On a List Variant of the Multiplicative 1-2-3 Conjecture. Graphs and Combinatorics, 38(3):88, 2022.
    16. J53. J. Bensmail, F. Fioravantes, N. Nisse. On Proper Labellings of Graphs with Minimum Label Sum. Algorithmica, 84:1030-1063, 2022.
    17. J52. J. Bensmail, F. Mc Inerney, K. Szabo Lyngsie. On {a,b}-edge-weightings of bipartite graphs with odd a,b. Discussiones Mathematicae Graph Theory, 42(1):159-185, 2022.
    18. J51. J. Bensmail, S. Das, S. Nandi, T. Pierron, S. Sen, É. Sopena. On the signed chromatic number of some classes of graphs. Discrete Mathematics, 345:112664, 2022.
    19. J50. J. Bensmail, H. Hocquard, D. Lajou, É. Sopena. Further Evidence Towards the Multiplicative 1-2-3 Conjecture. Discrete Applied Mathematics, 307:135-144, 2022.
    20. J49. J. Bensmail, F. Fioravantes, F. Mc Inerney. On the Role of 3s for the 1-2-3 Conjecture. Theoretical Computer Science, 892:238-257, 2021.
    21. J48. J. Bensmail, F. Fioravantes, F. Mc Inerney, N. Nisse. Further Results on an Equitable 1-2-3 Conjecture. Discrete Applied Mathematics, 297:1-20, 2021.
    22. J47. J. Bensmail, F. Mc Inerney. On Generalisations of the AVD Conjecture to Digraphs. Graphs and Combinatorics, 37:545-558, 2021.
    23. J46. J. Bensmail, F. Fioravantes. On BMRN*-colouring of planar digraphs. Discrete Mathematics & Theoretical Computer Science, 23(1), 2021, #4.
    24. J45. A. Arroyo, J. Bensmail, R.B. Richter. Extending Drawings of Graphs to Arrangements of Pseudolines. Journal of Computational Geometry, 12(2):3-24, 2021.
    25. J44. J. Bensmail, B. Li, B. Li. An injective version of the 1-2-3 Conjecture. Graphs and Combinatorics, 37:281-311, 2021.
    26. J43. J. Bensmail, S. Das, S. Nandi, T. Pierron, S. Paul, S. Sen, É. Sopena. Pushable chromatic number of graphs with degree constraints. Discrete Mathematics, 344(1):112151, 2021.
    27. J42. J. Bensmail, B. Li, B. Li, N. Nisse. On Minimizing the Maximum Color for the 1-2-3 Conjecture. Discrete Applied Mathematics, 289:32-51, 2021.
    28. J41. J. Bensmail, F. Dross, N. Nisse. Decomposing degenerate graphs into locally irregular subgraphs. Graphs and Combinatorics, 36:1869–1889, 2020.
    29. J40. J. Bensmail, D. Mazauric, F. Mc Inerney, N. Nisse, S. Pérennes. Sequential Metric Dimension. Algorithmica, 82:2867–2901, 2020.
    30. J39. J. Bensmail, K. Szabo Lyngsie. 1-2-3 Conjecture in Digraphs: More Results and Directions. Discrete Applied Mathematics, 284:124-137, 2020.
    31. J38. J. Bensmail, S. Nandi, M. Roy, S. Sen. Classification of edge-critical underlying absolute planar cliques for signed graphs. Australasian Journal of Combinatorics, 77(1):117-135, 2020.
    32. J37. J. Bensmail, F. Dross, H. Hocquard, É. Sopena. From light edges to strong edge-colouring of 1-planar graphs. Discrete Mathematics & Theoretical Computer Science, 22(1), 2020, #2.
    33. J36. J. Bensmail. On the 2-edge-coloured chromatic number of grids. Australasian Journal of Combinatorics, 75(3):365-384, 2019.
    34. J35. O. Baudon, J. Bensmail, H. Hocquard, M. Senhaji, É. Sopena. Edge Weights and Vertex Colours: Minimizing Sum Count. Discrete Applied Mathematics, 270:13-24, 2019.
    35. J34. J. Bensmail, J. Przybyło. Decomposability of graphs into subgraphs fulfilling the 1-2-3 Conjecture. Discrete Applied Mathematics, 268:1-9, 2019.
    36. J33. J. Bensmail, T. Blanc, N. Cohen, F. Havet, L. Rocha. Backbone colouring and algorithms for TDMA scheduling. Discrete Mathematics & Theoretical Computer Science, 21(3), 2019, #24.
    37. J32. J. Bensmail, A. Harutyunyan, T.-N. Le, S. Thomassé. Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture. Combinatorica, 39(2):239-263, 2019.
    38. J31. O. Baudon, J. Bensmail, T. Davot, H. Hocquard, J. Przybyło, M. Senhaji, É. Sopena, M. Woźniak. A general decomposition theory for the 1-2-3 Conjecture and locally irregular decompositions. Discrete Mathematics & Theoretical Computer Science, 21(1), 2019, #2.
    39. J30. J. Bensmail. A 1-2-3-4 result for the 1-2-3 Conjecture in 5-regular graphs. Discrete Applied Mathematics, 257:31-39, 2019.
    40. J29. O. Baudon, J. Bensmail, M. Senhaji, É. Sopena. Neighbour-Sum-2-Distinguishing Edge-Weightings: Doubling the 1-2-3 Conjecture. Discrete Applied Mathematics, 251:83-92, 2018.
    41. J28. J. Bensmail, V. Garnero, N. Nisse. On improving matchings in trees, via bounded-length augmentations. Discrete Applied Mathematics, 250:110-129, 2018.
    42. J27. O. Baudon, J. Bensmail, J. Przybyło, M. Woźniak. On locally irregular decompositions and the 1-2 Conjecture in digraphs. Discrete Mathematics & Theoretical Computer Science, 20(2), 2018, #7.
    43. J26. O. Baudon, J. Bensmail, H. Hocquard, M. Senhaji, É. Sopena. On locally irregular decompositions of subcubic graphs. Opuscula Mathematica, 38(6):795-817, 2018.
    44. J25. J. Bensmail, N. Brettell. Orienting edges to fight fire in graphs. Australasian Journal of Combinatorics, 71(1):12-42, 2018.
    45. J24. J. Bensmail, A. Harutyunyan, N.K. Le. List coloring digraphs. Journal of Graph Theory, 87(4):492-508, 2018.
    46. J23. J. Bensmail, A. Harutyunyan, N.K. Le, B. Li, N. Lichiardopol. Disjoint cycles of different lengths in graphs and digraphs. Electronic Journal of Combinatorics, 24(4):#P4.37, 2017.
    47. J22. J. Bensmail, S. Nandi, S. Sen. On oriented cliques with respect to push operation. Discrete Applied Mathematics, 232:50-63, 2017.
    48. J21. J. Bensmail, M. Senhaji, K. Szabo Lyngsie. On a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture. Discrete Mathematics & Theoretical Computer Science, 19(1), 2017, #22.
    49. J20. J. Bensmail, C. Duffy, S. Sen. Analogues of cliques for (m,n)-colored mixed graphs. Graphs and Combinatorics, 33(4):735-750, 2017.
    50. J19. J. Bensmail, A. Harutyunyan, T.-N. Le, M. Merker, S. Thomassé. A proof of the Barát-Thomassen conjecture. Journal of Combinatorial Theory, Series B, 124:39-55, 2017.
    51. J18. J. Bensmail. On q-power cycles in cubic graphs. Discussiones Mathematicae Graph Theory, 37:211-220, 2017.
    52. J17. O. Baudon, J. Bensmail, F. Foucaud, M. Pilśniak. Structural properties of recursively partitionable graphs with connectivity 2. Discussiones Mathematicae Graph Theory, 37:89-115, 2017.
    53. J16. E. Barme, J. Bensmail, J. Przybyło, M. Woźniak. On a directed variation of the 1-2-3 and 1-2 Conjectures. Discrete Applied Mathematics, 217(2):123-131, 2017.
    54. J15. J. Bensmail, M. Merker, C. Thomassen. Decomposing graphs into a constant number of locally irregular subgraphs. European Journal of Combinatorics, 60:124-134, 2017.
    55. J14. J. Bensmail, G. Renault. Decomposing oriented graphs into six locally irregular oriented graphs. Graphs and Combinatorics, 32(5):1707-1721, 2016.
    56. J13. J. Bensmail, B. Stevens. Edge-partitioning graphs into regular and locally irregular components. Discrete Mathematics & Theoretical Computer Science, 17(3):43-58, 2016.
    57. J12. J. Bensmail, R. Duvignau, S. Kirgizov. The complexity of deciding whether a graph admits an orientation with fixed weak diameter. Discrete Mathematics & Theoretical Computer Science, 17(3):31-42, 2016.
    58. J11. J. Bensmail. On three polynomial kernels of sequences for arbitrarily partitionable graphs. Discrete Applied Mathematics, 202:19-29, 2016.
    59. J10. J. Bensmail, A. Lagoutte, P. Valicov. Strong edge-coloring of (3, Δ)-bipartite graphs. Discrete Mathematics, 339(1):391-398, 2016.
    60. J9. J. Bensmail. On the complexity of partitioning a graph into a few connected subgraphs. Journal of Combinatorial Optimization, 30(1):174-187, 2015.
    61. J8. O. Baudon, J. Bensmail, J. Przybyło, M. Woźniak. On decomposing regular graphs into locally irregular subgraphs. European Journal of Combinatorics, 49:90-104, 2015.
    62. J7. O. Baudon, J. Bensmail, É. Sopena. On the complexity of determining the irregular chromatic index of a graph. Journal of Discrete Algorithms, 30:113-127, 2015.
    63. J6. O. Baudon, J. Bensmail, É. Sopena. An oriented version of the 1-2-3 Conjecture. Discussiones Mathematicae Graph Theory, 35(1):141-156, 2015.
    64. J5. O. Baudon, J. Bensmail, É. Sopena. Partitioning Harary graphs into connected subgraphs containing prescribed vertices. Discrete Mathematics & Theoretical Computer Science, 16(3):263-278, 2014.
    65. J4. J. Bensmail, A. Harutyunyan, H. Hocquard, P. Valicov. Strong edge-colouring of sparse planar graphs. Discrete Applied Mathematics, 179:229-234, 2014.
    66. J3. O. Baudon, J. Bensmail, R. Kalinowski, A. Marczyk, J. Przybyło, M. Woźniak. On the Cartesian product of an arbitrarily partitionable graph and a traceable graph. Discrete Mathematics & Theoretical Computer Science, 16(1):225-232, 2014.
    67. J2. O. Baudon, J. Bensmail, J. Przybyło, M. Woźniak. Partitioning powers of traceable or Hamiltonian graphs. Theoretical Computer Science, 520:133-137, 2014.
    68. J1. J. Bensmail. On the longest path in a recursively partitionable graph. Opuscula Mathematica, 33(4):631-640, 2013.

    69. C11. J. Bensmail, H. Hocquard, P.-M. Marcille. The Weak (2,2)-Labelling Problem for graphs with forbidden induced structures. CALDAM 2023, Gandhinagar, India.
    70. C10. J. Bensmail, H. Hocquard, D. Lajou, É. Sopena. A proof of the Multiplicative 1-2-3 Conjecture. CALDAM 2022, Puducherry, India.
    71. C9. J. Bensmail, F. Fioravantes, F. Mc Inerney, N. Nisse. The Largest Connected Subgraph Game. WG 2021, Warsaw, Poland.
    72. C8. J. Bensmail, F. Fioravantes, F. Mc Inerney. On the Role of 3's for the 1-2-3 Conjecture. CIAC 2021, Larnaca, Cyprus.
    73. C7. J. Bensmail, F. Fioravantes, N. Nisse. On Proper Labellings of Graphs with Minimum Label Sum. IWOCA 2020, Bordeaux, France.
    74. C6. A. Arroyo, J. Bensmail, R.B. Richter. Extending Drawings of Graphs to Arrangements of Pseudolines. SoCG 2020, Zürich, Switzerland.
    75. C5. J. Bensmail, F. Mc Inerney, N. Nisse. Metric Dimension: from Graphs to Oriented Graphs. LAGOS 2019, Belo Horizonte, Brazil.
    76. C4. J. Bensmail, D. Mazauric, F. Mc Inerney, N. Nisse, S. Pérennes. Sequential Metric Dimension. WAOA 2018, Helsinki, Finland.
    77. C3. J. Bensmail, V. Garnero, N. Nisse, A. Salch, V. Weber. Recovery of disrupted airline operations using k-Maximum Matching in graphs. LAGOS 2017, Marseille, France.
    78. C2. J. Bensmail, M. Bonamy, H. Hocquard. Strong edge coloring sparse graphs. EuroComb 2015, Bergen, Norway.
    79. C1. J. Bensmail. Complexity of determining the irregular chromatic index of a graph. EuroComb 2013, Pisa, Italy.

    80. S4. J. Bensmail, H. Hocquard, P.-M. Marcille. The Weak (2,2)-Labelling Problem for graphs with forbidden induced structures. 2022.
    81. S3. J. Bensmail, S. Das, S. Nandi, A. Nandy, T. Pierron, S. Prabhu, S. Sen. Oriented Total-Coloring of Oriented Graphs. 2022.
    82. S2. J. Bensmail. Some Properties of Minimal Arbitrarily Partitionable Graphs. 2022.
    83. S1. J. Bensmail, T. Das, D. Lajou, S. Nandi, S. Sen. On the pushable chromatic number of various types of grids. 2022.

    84. T3. A contribution to distinguishing labellings of graphs. Habilitation thesis. Université Côte d'Azur. 2020.
    85. T2. Partitions and decompositions of graphs. Ph.D. thesis. Université de Bordeaux. 2014.
    86. T1. Préaffectation de sommets dans les graphes arbitrairement partitionnables (in French). Master thesis. Université de Bordeaux. 2011.

  • Teaching:

    Since 2016/2017, I teach at the département QLIO of IUT Nice Côte d'Azur:

    • Since 2022-2023: Algorithmique et programmation avancées (BUT QLIO S3).
    • Since 2018-2019: Sécurité des systèmes d'information (LP MPL).

    • From 2017-2018 to 2021-2022: Systèmes de gestion de bases de données (DUT QLIO S3).
    • From 2016-2017 to 2021-2022: Recherche opérationnelle (DUT QLIO S4).
    • 2019-2020: Informatique décisionnelle (LP MPL+GPI).
    • 2016-2017: Systèmes d'information et logistique (DUT QLIO S3).

    Since 2019-2020, I am in charge of the LP MPL.


    Étudiant en LP GPI ou MPL ? Quelques informations pratiques sont résumées ici.


    Some materials of my previous teaching activities are gathered on this page.


  • Code-related stuff:

    • A nice page for playing with augmenting paths (w/ J. Belmon & V. Garnero)...
    • ... slight modifications: Resigning graphs, Pushing oriented graphs, Deriving sums from 3-edge-weightings.
    • A list of all non-isomorphic planar push cliques (w/ S. Nandi & S. Sen).
    • A similar one for non-isomorphic underlying absolute planar cliques of signed graphs (w/ S. Nandi, M. Roy & S. Sen).
    • Some algs I use for solving the Rubik's cube :) . I average something like 15/16 sec. Example solve: