On star and biclique edge-colorings

详细信息    查看全文

• 作者：Simone Dantas ; Marina Groshaus ; André ; Guedes ; Raphael C. S. Machado ; Bernard Ries and Diana Sasaki
• 刊名：International Transactions in Operational Research
• 出版年：2017
• 出版时间：January/March 2017
• 年：2017
• 卷：24
• 期：1-2
• 页码：339-346
• 全文大小：275K
• ISSN：1475-3995

文摘

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: K₃-free graphs, chordal bipartite graphs, powers of paths, and powers of cycles.