Premium
Strong chromatic index and Hadwiger number
Author(s) -
Batenburg Wouter Cames,
Joannis de Verclos Rémi,
Kang Ross J.,
Pirot François
Publication year - 2022
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22788
Subject(s) - mathematics , conjecture , combinatorics , edge coloring , chromatic scale , clique , minor (academic) , multigraph , clique number , index (typography) , simple (philosophy) , discrete mathematics , graph , computer science , line graph , political science , law , graph power , philosophy , epistemology , world wide web
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 ) Δ .