DIKUL - logo
E-resources
Peer reviewed Open access
  • Strong chromatic index and ...
    Batenburg, Wouter Cames; Joannis de Verclos, Rémi; Kang, Ross J.; Pirot, François

    Journal of graph theory, July 2022, Volume: 100, Issue: 3
    Journal Article

    We investigate the effect of a fixed forbidden clique minor upon the strong chromatic index, both in multigraphs and in simple graphs. We conjecture for each k ≥ 4 that any K k‐minor‐free multigraph of maximum degree Δ has strong chromatic index at most 3 2 ( k − 2 ) Δ. We present a construction certifying that if true the conjecture is asymptotically sharp as Δ → ∞. In support of the conjecture, we show it in the case k = 4 and prove the statement for strong clique number in place of strong chromatic index. By contrast, we make a basic observation that for K k‐minor‐free simple graphs, the problem of strong edge‐colouring is “between” Hadwiger's Conjecture and its fractional relaxation. For k ≥ 5, we also show that K k‐minor‐free multigraphs of edge‐diameter at most 2 have strong clique number at most ( k − 1 2 ) Δ.