Biclique edge-choosability in some classes of graphs∗

• Gabriel A. G. Sobral
• Marina Groshaus
• André L. P. Guedes

DOI: https://doi.org/10.5753/etc.2017.3203

Resumo

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 K3free 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 K3-free and chordal bipartite graphs for any given 2-list assignment to edges.