Navegar

Colección

Datos Estadísticas

Artículo

Groshaus, M.; Soulignac, F.J.; Terlisky, P. "The star and biclique coloring and choosability problems" (2014) Journal of Graph Algorithms and Applications. 18(3):347-383
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 a graph G is an induced complete bipartite graph. A star of G is a biclique contained in the closed neighborhood of a vertex. A star (biclique) k-coloring of G is a k-coloring of G that contains no monochromatic maximal stars (bicliques). Similarly, for a list assignment L of G, a star (biclique) L-coloring is an L-coloring of G in which no maximal star (biclique) is monochromatic. If G admits a star (biclique) L- coloring for every k-list assignment L, then G is said to be star (biclique) k-choosable. In this article we study the computational complexity of the star and biclique coloring and choosability problems. Specifically, we prove that the star (biclique) k-coloring and k-choosability problems are Σp2-complete and IIp3-complete for k > 2, respectively, even when the input graph contains no induced C4 or Kk+2. Then, we study all these problems in some related classes of graphs, including H-free graphs for every H on three vertices, graphs with restricted diamonds, split graphs, and threshold graphs.

Registro:

Documento: Artículo
Título:The star and biclique coloring and choosability problems
Autor:Groshaus, M.; Soulignac, F.J.; Terlisky, P.
Filiación:Departamento de Computación, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina
CONICET, Argentina
Universidad Nacional de Quilmes, Buenos Aires, Argentina
Año:2014
Volumen:18
Número:3
Página de inicio:347
Página de fin:383
DOI: http://dx.doi.org/10.7155/jgaa.00326
Título revista:Journal of Graph Algorithms and Applications
Título revista abreviado:J. Graph Algorithms and Appl.
ISSN:15261719
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15261719_v18_n3_p347_Groshaus

Referencias:

  • Amilhastre, J., Vilarem, M.C., Janssen, P., Complexity of minimum biclique cover and minimum biclique decomposition for bipartite dominofree graphs (1998) Discrete Appl. Math, 86 (2-3), pp. 125-144. , doi:10.1016/S0166-218X(98)00039-0
  • Bacsó, G., Gravier, S., Gyárfás, A., Preissmann, M., Sebo, A., Coloring the maximal cliques of graphs (2004) SIAM J. Discrete Math, 17 (3), pp. 361-376. , electronic, doi:10.1137/S0895480199359995
  • Cerioli, M.R., Korenchendler, A.L., Clique-coloring circular-arc graphs (2009) LAGOS'09|V Latin-American Algorithms, Graphs and Optimization Symposium, 35, pp. 287-292. , T. M. Liebling, J. L. Szwarcfiter, C. E. Ferreira, and F. Protti, editors, Electron. Notes Discrete Math, Elsevier Sci. B. V., Amsterdam, doi:10.1016/j.endm.2009.11.047
  • Défossez, D., Clique-coloring some classes of odd-hole-free graphs (2006) J. Graph Theory, 53 (3), pp. 233-249. , doi:10.1002/jgt.20177
  • Défossez, D., Complexity of clique-coloring odd-hole-free graphs (2009) J. Graph Theory, 62 (2), pp. 139-156. , doi:10.1002/jgt.20387
  • Eguía, M., Soulignac, F.J., Hereditary biclique-Helly graphs: Recognition and maximal biclique enumeration (2013) Discrete Math. Theor. Comput. Sci, 15 (1), pp. 55-74. , http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1826, URL
  • Eiter, T., Gottlob, G., (1995) Note On the Complexity of Some Eigenvector Problems, , Technical Report CD-TR 95/89, Christian Doppler Labor für Expertensyteme, TU Vienna
  • Farber, M., On diameters and radii of bridged graphs (1989) Discrete Math, 73 (3), pp. 249-260. , doi:10.1016/0012-365X(89)90268-9
  • Garey, M.R., Johnson, D.S., (1979) Computers and Intractability, , W. H. Freeman and Co., San Francisco, Calif
  • Golumbic, M.C., (2004) Algorithmic Graph Theory and Perfect Graphs, 57. , Annals of Discrete Mathematics. Elsevier Science B.V., Amsterdam, second edition
  • Gravier, S., Hoàng, C.T., Maffray, F., Coloring the hypergraph of maximal cliques of a graph with no long path (2003) Discrete Math, 272 (2-3), pp. 285-290. , doi:10.1016/S0012-365X(03)00197-3
  • Groshaus, M., Montero, L.P., On the iterated biclique operator (2013) J. Graph Theory, 73 (2), pp. 181-190. , doi:10.1002/jgt.21666
  • Groshaus, M., Szwarc-Ter, J.L., Biclique-Helly graphs (2007) Graphs Combin, 23 (6), pp. 633-645. , doi:10.1007/s00373-007-0756-6
  • Groshaus, M., Szwarc-Ter, J.L., Biclique graphs and biclique matrices (2010) J. Graph Theory, 63 (1), pp. 1-16. , doi:10.1002/jgt.20442
  • Gutner, S., Tarsi, M., Some results on (a: B)-choosability (2009) Discrete Math, 309 (8), pp. 2260-2270. , doi:10.1016/j.disc.2008.04.061
  • Kratochvíl, J., Tuza, Z., On the complexity of bicoloring clique hypergraphs of graphs (2002) J. Algorithms, 45 (1), pp. 40-54. , doi:10.1016/S0196-6774(02)00221-3
  • Lovász, L., Coverings and colorings of hypergraphs (1973) Proc. Fourth Southeastern Conference On Combinatorics, Graph Theory, and Computing, pp. 3-12. , F. Hoffman, R. B. Levow, and R. S. D. Thomas, editors, Winnipeg, Man, Utilitas Math
  • Macêdo, F.H.B., Dantas, S., Machado, R.C.S., de Figueiredo, C.M.H., Biclique-colouring powers of paths and powers of cycles (2012) Proc. 11th Cologne-Twente Workshop On Graphs and Combinatorial Optimization, pp. 134-138. , A. Brieden, Z.-K. Görgülü, T. Krug, E. Kropat, S. Meyer-Nieberg, G. Mihelcic, and S. W. Pickl, editors, CTW 2012, arXiv:1203.2543
  • Macêdo, F.H.B., Machado, R.C.S., de Figueiredo, C.M.H., Cliquecolouring and biclique-colouring unichord-free graphs (2012) LATIN 2012: Theoretical Informatics, 7256. , D. Fernández- Baca, editor, Lecture Notes in Computer Science, pages 530-541. Springer Berlin Heidelberg, doi:10.1007/978-3-642-29344-3_45
  • Maffray, F., Preissmann, M., On the NP-completeness of the kcolorability problem for triangle-free graphs (1996) Discrete Math, 162 (1-3), pp. 313-317. , doi:10.1016/S0012-365X(97)89267-9
  • Mahadev, N.V.R., Peled, U.N., (1995) Threshold Graphs and Related Topics, Volume 56 of Annals of Discrete Mathematics, , North-Holland Publishing Co., Amsterdam
  • Marx, D., Complexity of clique coloring and related problems (2011) Theoret. Comput. Sci, 412 (29), pp. 3487-3500. , doi:10.1016/j.tcs.2011.02. 038
  • Mohar, B., Škrekovski, R., The Grötzsch theorem for the hypergraph of maximal cliques (1999) Electron. J. Combin., 6:Research Paper, 26, p. 13. , http://www.combinatorics.org/Volume_6/Abstracts/v6i1r26.html, electronic, URL
  • Papadimitriou, C.H., (1994) Computational Complexity, , Addison-Wesley Publishing Company, Reading, MA
  • Prisner, E., Bicliques in graphs. I. Bounds on their number (2000) Combinatorica, 20 (1), pp. 109-117. , doi:10.1007/s004930070035
  • Terlisky, P., (2010) Biclique-coloreo De Grafos, , http://dc.uba.ar/inv/tesis/licenciatura/2010/terliski, Master's thesis, Universidad de Buenos Aires, URL
  • Tuza, Z., Covering of graphs by complete bipartite subgraphs: Complexity of 0-1 matrices (1984) Combinatorica, 4 (1), pp. 111-116. , doi:10.1007/BF02579163

Citas:

---------- APA ----------
Groshaus, M., Soulignac, F.J. & Terlisky, P. (2014) . The star and biclique coloring and choosability problems. Journal of Graph Algorithms and Applications, 18(3), 347-383.
http://dx.doi.org/10.7155/jgaa.00326
---------- CHICAGO ----------
Groshaus, M., Soulignac, F.J., Terlisky, P. "The star and biclique coloring and choosability problems" . Journal of Graph Algorithms and Applications 18, no. 3 (2014) : 347-383.
http://dx.doi.org/10.7155/jgaa.00326
---------- MLA ----------
Groshaus, M., Soulignac, F.J., Terlisky, P. "The star and biclique coloring and choosability problems" . Journal of Graph Algorithms and Applications, vol. 18, no. 3, 2014, pp. 347-383.
http://dx.doi.org/10.7155/jgaa.00326
---------- VANCOUVER ----------
Groshaus, M., Soulignac, F.J., Terlisky, P. The star and biclique coloring and choosability problems. J. Graph Algorithms and Appl. 2014;18(3):347-383.
http://dx.doi.org/10.7155/jgaa.00326