On incidence coloring of complete multipartite and semicubic bipartite graphs
Robert Janczewski, Anna Małafiejska, Michał Małafiejski · Discussiones Mathematicae Graph Theory · 2017
In the paper, we show that the incidence chromatic number i of a complete k-partite graph is at most +2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to +1 if and only if the smallest part has only one vertex (i.e., = n -1). Formally, for a complete k-partite graph G = K r1,r2,...,r k with the size of the smallest part equal to r 1 1 we have