Abstract:
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. © 2016 The Authors. International Transactions in Operational Research © 2016 International Federation of Operational Research Societies Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148, USA.
Registro:
Documento: |
Artículo
|
Título: | On star and biclique edge-colorings |
Autor: | Dantas, S.; Groshaus, M.; Guedes, A.; Machado, R.C.S.; Ries, B.; Sasaki, D. |
Filiación: | Departamento de Análise, Instituto de Matemática e Estatística, Universidade Federal Fluminense, Brazil Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina Setor de Ciências Exatas, Departamento de Informática, Universidade Federal do Paraná, Brazil Instituto Nacional de Metrologia, Qualidade e Tecnologia (Inmetro), Brazil Department of Informatics, University of Fribourg, Switzerland LAMSADE – CNRS UMR 7243 –, Université Paris Dauphine, France Departamento de Matemática Aplicada, Instituto de Matemática e Estatística, Universidade do Estado do Rio de Janeiro, Brazil
|
Palabras clave: | biclique edge-coloring; NP-hard; star edge-coloring; Coloring; Polynomial approximation; Set theory; Stars; Bicliques; Chordal bipartite graph; Complete bipartite graphs; Edge coloring; Free graphs; NP-hard; Polynomial-time algorithms; Two-color; Graph theory |
Año: | 2017
|
Volumen: | 24
|
Número: | 1-2
|
Página de inicio: | 339
|
Página de fin: | 346
|
DOI: |
http://dx.doi.org/10.1111/itor.12307 |
Título revista: | International Transactions in Operational Research
|
Título revista abreviado: | Int. Trans. Oper. Res.
|
ISSN: | 09696016
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09696016_v24_n1-2_p339_Dantas |
Referencias:
- Campos, C.N., de Mello, C.P., A result on the total coloring of powers of cycles (2007) Discrete Applied Mathematics, 155, pp. 585-597
- Cerioli, M.R., Posner, D.F.D., On L(2, 1)-coloring split, chordal bipartite, and weakly chordal graphs (2012) Discrete Applied Mathematics, 160 (18), pp. 2655-2661
- Culberson, J., (2000) Overview of the smallk graph coloring program, , http://webdocs.cs.ualberta.ca/∼joe/Coloring/Colorsrc/smallk.html, (accessed May 10, 2016)
- Dabrowski, K.K., Lozin, V., Raman, R., Ries, B., Colouring vertices of triangle-free graphs without forests (2012) Discrete Mathematics, 312 (7), pp. 1372-1385
- Faure, N., Chrétienne, P., Gourdin, E., Sourd, F., Biclique completion problems for multicast network design (2014) Discrete Optimization, 4 (3-4), pp. 360-377
- Groshaus, M., Soulignac, F.J., Terlisky, P., Star and biclique coloring and choosability (2014) Journal of Graph Algorithms and Applications, 18 (3), pp. 347-383
- Gualandi, S., Maffioli, F., Magni, C., A branch-and-price approach to k-clustering minimum biclique completion problem (2013) International Transactions in Operational Research, 20, pp. 101-117
- Kratochvíl, J., Tuza, Z., On the complexity of bicoloring clique hypergraphs of graphs (2002) Journal of Algorithms, 45 (1), pp. 40-54
- Luiz, A.G., Campos, C.N., Dantas, S., Sasaki, D., The 1,2-conjecture for powers of cycles (2015) Proceedings of LAGOS 2015., Electronic Notes in Discrete Mathematics, 50, pp. 83-88
- Filho, H.B., Dantas, S., Machado, R.C.S., Figueiredo, C.M.H., Biclique-colouring verification complexity and biclique-colouring power graphs (2015) Discrete Applied Mathematics, 192, pp. 65-76. , Macêdo
- Macêdo Filho, H.B., Machado, R.C.S., Figueiredo, C.M.H., Clique-colouring and biclique-colouring unichord-free graphs (2012) Proceedings of LATIN 2012 Lecture Notes in Computer Science, 7256, pp. 530-541
- Marx, D., Complexity of clique coloring and related problems (2011) Theoretical Computer Science, 412 (29), pp. 3487-3500
- Schaefer, T.J., (1978) Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 216-226. , The complexity of satisfiability problems., Association for Computing Machinery, New York
- Zhang, Y., Phillips, C.A., Rogers, G.L., Baker, E.J., Chesler, E.J., Langston, M.A., On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types (2014) BMC Bioinformatics, 15 (110), pp. 1-18
Citas:
---------- APA ----------
Dantas, S., Groshaus, M., Guedes, A., Machado, R.C.S., Ries, B. & Sasaki, D.
(2017)
. On star and biclique edge-colorings. International Transactions in Operational Research, 24(1-2), 339-346.
http://dx.doi.org/10.1111/itor.12307---------- CHICAGO ----------
Dantas, S., Groshaus, M., Guedes, A., Machado, R.C.S., Ries, B., Sasaki, D.
"On star and biclique edge-colorings"
. International Transactions in Operational Research 24, no. 1-2
(2017) : 339-346.
http://dx.doi.org/10.1111/itor.12307---------- MLA ----------
Dantas, S., Groshaus, M., Guedes, A., Machado, R.C.S., Ries, B., Sasaki, D.
"On star and biclique edge-colorings"
. International Transactions in Operational Research, vol. 24, no. 1-2, 2017, pp. 339-346.
http://dx.doi.org/10.1111/itor.12307---------- VANCOUVER ----------
Dantas, S., Groshaus, M., Guedes, A., Machado, R.C.S., Ries, B., Sasaki, D. On star and biclique edge-colorings. Int. Trans. Oper. Res. 2017;24(1-2):339-346.
http://dx.doi.org/10.1111/itor.12307