On star and biclique edge-colorings
- Dantas, Simone Universidade Federal Fluminense
- Groshaus, Marina Universidad de Buenos Aires
- Guedes , André Universidade Federal do Parana
- C.S. Machado, Raphael Qualidade e Tecnologia (Inmetro)
- Ries, Bernard University of Fribourg
- Sasaki, Diana Universidade do Estado do Rio de Janeiro
-
2017
Published in:
- International Transactions in Operational Research. - 2017, vol. 24, p. 339-346
English
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.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Economics
- License
- License undefined
- Identifiers
-
- RERO DOC 324393
- DOI 10.1111/itor.12307
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307798
Statistics
Document views: 36
File downloads:
- biclique_rero.pdf: 77