
doi: 10.7151/dmgt.1456
We propose the following problem. For some \(k\geq 1\), a graph \(G\) is to be properly edge coloured such that any two adjacent vertices share at most \(k\) colours. We call this the \(k\)-intersection edge colouring. The minimum number of colours sufficient to guarantee such a colouring is the \(k\)-intersection chromatic index and is denoted \(\chi_k'(G)\). Let \(f_k\) be defined by \[ f_k(\Delta)= \max_{G:\Delta(G)=\Delta} \{\chi_k'(G)\}. \] We show that \(f_k(\Delta)= \Theta(\frac{\Delta^2}{k})\). We also discuss some open problems.
Coloring of graphs and hypergraphs, \(k\)-intersection edge colouring, graph theory, probabilistic method, Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
Coloring of graphs and hypergraphs, \(k\)-intersection edge colouring, graph theory, probabilistic method, Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
