TY - JOUR
AU - Sobral, Gabriel A. G.
AU - Groshaus, Marina
AU - Guedes, André L. P.
PY - 2017
TI - Biclique edge-choosability in some classes of graphs
JF - Anais do Encontro de Teoria da Computação (ETC); 2017: Anais do II Encontro de Teoria da Computação
DO - 10.5753/etc.2017.3203
KW -
N2 - 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.
UR - https://sol.sbc.org.br/index.php/etc/article/view/3203