Biclique edge-choosability in some classes of graphs - Sobral, Gabriel A. G.; Groshaus, Marina; Guedes, André L. P. (Anais do Encontro de Teoria da Computação (ETC), 2017)
In this paper we study the problem of coloring the edges of a graph for any k-list assignment such that there is no maximal monochromatic biclique, in other words, the k-biclique edge-choosability problem. We prove that the K 3 -free graphs that are not odd cycles are 2-star edge-choosable, chordal bipartite graphs are 2-biclique edge-choosable and we present a lower bound for the biclique choice index of power of cycles and power of paths. We also provide polynomial algorithms to compute a 2-biclique (star) edge-coloring for K 3 -free and chordal bipartite graphs for any given 2-list assignment to edges.