On star and biclique edge-colorings

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) edge-coloring 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.Fil: Dantas, Simone. Universidade Federal Fluminense; BrasilFil: Groshaus, Marina Esther. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Guedes, André. Universidade Federal do Paraná; BrasilFil: Machado, Raphael C. S.. Instituto Nacional de Metrologia, Qualidade e Tecnologia ; BrasilFil: Ries, Bernard. University of Fribourg; SuizaFil: Sasaki, Diana. Universidade Federal do Rio de Janeiro; Brasi