The star and biclique coloring and choosability problems
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...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Brown University
2014
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 07983caa a22006377a 4500 | ||
|---|---|---|---|
| 001 | PAPER-14610 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518204510.0 | ||
| 008 | 190411s2014 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-84904102244 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Groshaus, M. | |
| 245 | 1 | 4 | |a The star and biclique coloring and choosability problems |
| 260 | |b Brown University |c 2014 | ||
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Garey, M.R., Johnson, D.S., (1979) Computers and Intractability, , W. H. Freeman and Co., San Francisco, Calif | ||
| 504 | |a Golumbic, M.C., (2004) Algorithmic Graph Theory and Perfect Graphs, 57. , Annals of Discrete Mathematics. Elsevier Science B.V., Amsterdam, second edition | ||
| 504 | |a 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 | ||
| 504 | |a Groshaus, M., Montero, L.P., On the iterated biclique operator (2013) J. Graph Theory, 73 (2), pp. 181-190. , doi:10.1002/jgt.21666 | ||
| 504 | |a Groshaus, M., Szwarc-Ter, J.L., Biclique-Helly graphs (2007) Graphs Combin, 23 (6), pp. 633-645. , doi:10.1007/s00373-007-0756-6 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Papadimitriou, C.H., (1994) Computational Complexity, , Addison-Wesley Publishing Company, Reading, MA | ||
| 504 | |a Prisner, E., Bicliques in graphs. I. Bounds on their number (2000) Combinatorica, 20 (1), pp. 109-117. , doi:10.1007/s004930070035 | ||
| 504 | |a Terlisky, P., (2010) Biclique-coloreo De Grafos, , http://dc.uba.ar/inv/tesis/licenciatura/2010/terliski, Master's thesis, Universidad de Buenos Aires, URL | ||
| 504 | |a 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 | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a Departamento de Computación, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 593 | |a CONICET, Argentina | ||
| 593 | |a Universidad Nacional de Quilmes, Buenos Aires, Argentina | ||
| 700 | 1 | |a Soulignac, F.J. | |
| 700 | 1 | |a Terlisky, P. | |
| 773 | 0 | |d Brown University, 2014 |g v. 18 |h pp. 347-383 |k n. 3 |p J. Graph Algorithms and Appl. |x 15261719 |w (AR-BaUEN)CENRE-8790 |t Journal of Graph Algorithms and Applications | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-84904102244&doi=10.7155%2fjgaa.00326&partnerID=40&md5=e8128ceefbde1fea4540c9f848d29eb3 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.7155/jgaa.00326 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_15261719_v18_n3_p347_Groshaus |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15261719_v18_n3_p347_Groshaus |y Registro en la Biblioteca Digital |
| 961 | |a paper_15261719_v18_n3_p347_Groshaus |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 75563 | ||