Dantas, Simone Groshaus, Marina Guedes , André C.S. Machado, Raphael Ries, Bernard Sasaki, Diana 2017 A biclique of G is a maximal set of vertices that induces a complete bipartite subgraph Kp,q of G with at least one edge, and a star of a graph G is a maximal set of vertices that induces a complete bipartite graph K1,q. A biclique (resp. star) edge-coloring is a coloring of the edges of a graph with no monochromatic bicliques (resp. stars). We prove that the problem of determining whether a graph G has a biclique (resp. star) edgecoloring using two colors is NP-hard. Furthermore, we describe polynomial time algorithms for the problem in restricted classes: K3-free graphs, chordal bipartite graphs, powers of paths, and powers of cycles. application/pdf https://folia.unifr.ch/unifr/documents/307798 https://folia.unifr.ch/documents/307798/files/biclique_rero.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1111/itor.12307 info:eu-repo/semantics/openAccess License undefined International Transactions in Operational Research. - 2017, vol. 24, p. 339-346 star edge-coloring biclique edge-coloring NP-hard info:eu-repo/classification/udc/33 On star and biclique edge-colorings http://purl.org/coar/resource_type/c_6501