Artículo

Dantas, S.; Groshaus, M.; Guedes, A.; Machado, R.C.S.; Ries, B.; Sasaki, D."On star and biclique edge-colorings" (2017) International Transactions in Operational Research. 24(1-2):339-346
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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
Handle:http://hdl.handle.net/20.500.12110/paper_09696016_v24_n1-2_p339_Dantas
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