On the inclusion chromatic index of a graph
Jakub Przybyło, Jakub Kwaśny · Journal of Graph Theory · 2020
Abstract Let be the least number of colours necessary to properly colour the edges of a graph with minimum degree so that the set of colours incident with any vertex is not contained in a set of colours incident to any of its neighbours. We provide an infinite family of examples of graphs with , where is the maximum degree of , and we conjecture that for every connected graph with which is not isomorphic to . The equality here is attained, for example, for the family of complete bipartite graphs. Using a probabilistic argument we support this conjecture by proving that (for ) for any fixed , which implies that for large enough.