Navegar

Colección

Datos Estadísticas

Artículo

La versión final de este artículo es de uso interno de la institución.
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color is equal to the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. In previous works, polynomial time algorithms were found for recognizing coordinated graphs within some classes of graphs. In this paper we prove that the recognition problem for coordinated graphs is NP-hard, and it is NP-complete even when restricted to the class of {gem, C 4, odd hole}-free graphs with maximum degree four, maximum clique size three and at most three cliques sharing a common vertex. © 2008 Springer Science+Business Media, LLC.

Registro:

Documento: Artículo
Título:NP-hardness of the recognition of coordinated graphs
Autor:Soulignac, F.J.; Sueiro, G.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Palabras clave:Computational complexity; Coordinated graph recognition; NP-complete problems; {gem, C 4, odd hole}-free graphs
Año:2009
Volumen:169
Número:1
Página de inicio:17
Página de fin:34
DOI: http://dx.doi.org/10.1007/s10479-008-0392-4
Título revista:Annals of Operations Research
Título revista abreviado:Ann. Oper. Res.
ISSN:02545330
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v169_n1_p17_Soulignac

Referencias:

  • Bonomo, F., (2005) On Subclasses and Variations of Perfect Graphs, , PhD thesis, Departmento de Computación, FCEyN, Universidad de Buenos Aires, Buenos Aires
  • Bonomo, F., Durán, G., Groshaus, M., Szwarcfiter, J.L., On clique-perfect and K-perfect graphs (2006) Ars Combinatoria, 80, pp. 97-112
  • Bonomo, F., Partial characterizations of coordinated graphs: Line graphs and complements of forests (2006) ISMP'06
  • Bonomo, F., Durán, G., Groshaus, M., Coordinated graphs and clique graphs of clique-Helly perfect graphs (2007) Utilitas Mathematica, 72, pp. 175-191
  • Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs, I: Sublcasses of claw-free graphs (2008) Discrete Applied Mathematics, 156 (7), pp. 1058-1082
  • Bonomo, F., Durán, G., Soulignac, F., Sueiro, G., Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs (2008) Electronic Notes in Discrete Mathematics, 30, pp. 51-56
  • Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., Vuš ković, K., Recognizing Berge graphs (2005) Combinatorica, 25 (2), pp. 143-186
  • Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R., The strong perfect graph theorem (2006) Annals of Mathematics (2), 164 (1), pp. 51-229
  • Escalante, F., Über iterierte Clique-Graphen (1973) Abhandlungen Aus Dem Mathematischen Seminar der Universitat Hamburg, 39, pp. 59-68
  • Golumbic, M.C., (2004) Algorithmic Graph Theory and Perfect Graphs, , 2 Annals of discrete mathematics 57 North-Holland Amsterdam
  • Grötschel, M., Lovász, L., Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization (1981) Combinatorica, 1 (2), pp. 169-197
  • Guruswami, V., Rangan, C.P., Algorithmic aspects of clique-transversal and clique-independent sets (2000) Discrete Applied Mathematics, 100 (3), pp. 183-202
  • Maffray, F., Preissmann, M., On the NP-completeness of the k-colorability problem for triangle-free graphs (1996) Discrete Mathematics, 162 (13), pp. 313-317
  • Soulignac, F., Sueiro, G., Exponential families of minimally non-coordinated graphs (2006) The 2nd Latin-American Workshop on Cliques in Graphs

Citas:

---------- APA ----------
Soulignac, F.J. & Sueiro, G. (2009) . NP-hardness of the recognition of coordinated graphs. Annals of Operations Research, 169(1), 17-34.
http://dx.doi.org/10.1007/s10479-008-0392-4
---------- CHICAGO ----------
Soulignac, F.J., Sueiro, G. "NP-hardness of the recognition of coordinated graphs" . Annals of Operations Research 169, no. 1 (2009) : 17-34.
http://dx.doi.org/10.1007/s10479-008-0392-4
---------- MLA ----------
Soulignac, F.J., Sueiro, G. "NP-hardness of the recognition of coordinated graphs" . Annals of Operations Research, vol. 169, no. 1, 2009, pp. 17-34.
http://dx.doi.org/10.1007/s10479-008-0392-4
---------- VANCOUVER ----------
Soulignac, F.J., Sueiro, G. NP-hardness of the recognition of coordinated graphs. Ann. Oper. Res. 2009;169(1):17-34.
http://dx.doi.org/10.1007/s10479-008-0392-4