info:eu-repo/semantics/article
On star and biclique edge-colorings
Fecha
2017-01Registro en:
Dantas, Simone; Groshaus, Marina Esther; Guedes, André; Machado, Raphael C. S.; Ries, Bernard; et al.; On star and biclique edge-colorings; Wiley; International Transactions in Operational Research; 24; 1-2; 1-2017; 339-346
0969-6016
CONICET Digital
CONICET
Autor
Dantas, Simone
Groshaus, Marina Esther
Guedes, André
Machado, Raphael C. S.
Ries, Bernard
Sasaki, Diana
Resumen
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.