Navegar

Colección

Datos Estadísticas

Artículo

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 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. Coordinated graphs are a subclass of perfect graphs. The list of minimal forbidden induced subgraphs for the class of coordinated graphs is not known. In this paper, we present a partial result in this direction, that is, we characterize coordinated graphs by minimal forbidden induced subgraphs when the graph is either a line graph, or the complement of a forest. © 2008 Springer-Verlag.

Registro:

Documento: Artículo
Título:Partial characterizations of coordinated graphs: Line graphs and complements of forests
Autor:Bonomo, F.; Durán, G.; Soulignac, F.; Sueiro, G.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Pab. I (1428), Buenos Aires, Argentina
Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile
Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
CONICET, Buenos Aires, Argentina
Palabras clave:Complements of forests; Coordinated graphs; Line graphs; Perfect graphs; Complements of forests; Coordinated graphs; Forbidden induced subgraphs; Graph g; Induced subgraph; Line graphs; Non-empty intersections; Partial characterizations; Perfect graphs; Graph theory
Año:2009
Volumen:69
Número:2
Página de inicio:251
Página de fin:270
DOI: http://dx.doi.org/10.1007/s00186-008-0257-2
Título revista:Mathematical Methods of Operations Research
Título revista abreviado:Math Meth Opr Res
ISSN:14322994
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14322994_v69_n2_p251_Bonomo

Referencias:

  • Bonomo, F., Chudnovsky, M., Durán, G., Partial characterizations of clique-perfect graphs I: Sublcasses of claw-free graphs (2008) Discrete Appl Math, 156, pp. 1058-1082
  • Bonomo, F., Durán, G., Groshaus, M., Coordinated graphs and clique graphs of clique-Helly perfect graphs (2007) Util Math, 72, pp. 175-191
  • 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) Ann Math, 164, pp. 51-229
  • De Werra, D., On line perfect graphs (1978) Math Program, 15, pp. 236-238
  • Golumbic, M., Algorithmic graph theory and perfect graphs (2004) 2nd Edn. Annals of Discrete Mathematics, 57. , North-Holland, Amsterdam
  • Guruswami, V., Pandu Rangan, C., Algorithmic aspects of clique-transversal and clique-independent sets (2000) Discrete Appl Math, 100 (3), pp. 183-202
  • Konig, D., Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre (1916) Math Ann, 77, pp. 453-465
  • Konig, D., Graphok és Matrixok (1931) Matematikai És Fizikai Lapok, 38, pp. 116-119
  • Lehot, P., An optimal algorithm to detect a line graph and output its root graph (1974) J ACM, 21 (4), pp. 569-575
  • Maffray, F., Kernels in perfect line-graphs (1992) J Comb Theory ser B, 55, pp. 1-8
  • Prisner, E., Hereditary clique-Helly graphs (1993) J Comb Math Comb Comput, 14, pp. 216-220
  • Soulignac, F., Sueiro, G., (2006) Exponential Families of Minimally Non-coordinated Graphs, , submitted
  • Soulignac, F., Sueiro, G., NP-hardness of the recognition of coordinated graphs (2006) Ann Oper Res, , (in press). doi: 10.1007/s10479-008-0392-4
  • Trotter, L., Line perfect graphs (1977) Math Program, 12, pp. 255-259

Citas:

---------- APA ----------
Bonomo, F., Durán, G., Soulignac, F. & Sueiro, G. (2009) . Partial characterizations of coordinated graphs: Line graphs and complements of forests. Mathematical Methods of Operations Research, 69(2), 251-270.
http://dx.doi.org/10.1007/s00186-008-0257-2
---------- CHICAGO ----------
Bonomo, F., Durán, G., Soulignac, F., Sueiro, G. "Partial characterizations of coordinated graphs: Line graphs and complements of forests" . Mathematical Methods of Operations Research 69, no. 2 (2009) : 251-270.
http://dx.doi.org/10.1007/s00186-008-0257-2
---------- MLA ----------
Bonomo, F., Durán, G., Soulignac, F., Sueiro, G. "Partial characterizations of coordinated graphs: Line graphs and complements of forests" . Mathematical Methods of Operations Research, vol. 69, no. 2, 2009, pp. 251-270.
http://dx.doi.org/10.1007/s00186-008-0257-2
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Soulignac, F., Sueiro, G. Partial characterizations of coordinated graphs: Line graphs and complements of forests. Math Meth Opr Res. 2009;69(2):251-270.
http://dx.doi.org/10.1007/s00186-008-0257-2