On star and biclique edge-colorings

详细信息    查看全文

• 作者：Simone Dantas ; Marina Groshaus ; Andr&eacute ; 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 ta-equation-construct="true" class="math-equation-construct">ta-equation-image="true" class="math-equation-image">ta-equation-mathml="true" class="math-equation-mathml" style="display:none">th xmlns:mml="http://www.w3.org/1998/Math/MathML">ttp://www.wiley.com/namespaces/wiley" xmlns:wiley="http://www.wiley.com/namespaces/wiley/wiley" xmlns:cr="urn://wiley-online-library/content/render" xmlns="http://www.w3.org/1998/Math/MathML">Kp,qth> 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 ta-equation-construct="true" class="math-equation-construct">ta-equation-image="true" class="math-equation-image">ta-equation-mathml="true" class="math-equation-mathml" style="display:none">th xmlns:mml="http://www.w3.org/1998/Math/MathML">ttp://www.wiley.com/namespaces/wiley" xmlns:wiley="http://www.wiley.com/namespaces/wiley/wiley" xmlns:cr="urn://wiley-online-library/content/render" xmlns="http://www.w3.org/1998/Math/MathML">K1,qth>. 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.