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 circular-arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular-arc graphs by a list of minimal forbidden induced subgraphswhen the graph belongs to any of the following classes: P 4-free graphs, paw-free graphs, claw-free chordal graphs and diamond-free graphs. © 2009 Wiley Periodicals, Inc.

Registro:

Documento: Artículo
Título:Partial characterizations of circular-arc graphs
Autor:Bonomo, F.; Durán, G.; Grippo, L.N.; Safe, M.D.
Filiación:Conicet and Departamento de Computación FCEN, Universidad de Buenos Aires, Argentina
Departamento de Ingeniería Industrial FCFM, Universidad de chile, Universidad de Buenos Aires, Argentina
Palabras clave:Circular-arc graphs; Claw-free chordal graphs; Cographs; Diamond-free graphs; Paw-free graphs; Chordal graphs; Circular-arc graph; Circular-arc graphs; Claw-free; Claw-free chordal graphs; Cographs; Forbidden induced subgraphs; Free graphs; Intersection graph; Partial characterization; Paw-free graphs; Characterization; Diamonds; Cavity resonators
Año:2009
Volumen:61
Número:4
Página de inicio:289
Página de fin:306
DOI: http://dx.doi.org/10.1002/jgt.20379
Título revista:Journal of Graph Theory
Título revista abreviado:J. Graph Theory
ISSN:03649024
CODEN:JGTHD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v61_n4_p289_Bonomo

Referencias:

  • Bang-Jensen, J., Hell, P., On chordal proper circular arc graphs (1994) Discrete Math, 128, pp. 395-398
  • Chong-Keang, L., Yee-Hock, P., On graphs without multicliqual edges (1981) J Graph Theory, 5, pp. 443-451
  • Chudnovsky, M., Seymour, P., The structure of claw-free graphs (2005) Surveys in Combinatorics, 2005, pp. 153-171. , B. S. Webb, Editor, London Mathematical Society, Lecture Note Series 327, Cambridge University Press, Cambridge, UK
  • M. Conforti, (K4- e)-free graphs and star cutsets, Lect Notes Math 1403 (1989), 236-253; Corneil, D., Lerchs, H., Burlingham, L.S., Complement reducible graphs (1981) Discrete Appl Math, 3, pp. 163-174
  • Corneil, D., Perl, Y., Stewart, L., Cographs: Recognition, applications and algorithms (1984) Congr Numer, 43, pp. 249-258
  • Deng, X., Hell, P., Huang, J., Linear time representation algorithms for proper circular-arc graphs and proper interval graphs (1996) SIAM J Comput, 25, pp. 390-403
  • Durán, G., Gravano, A., McConnell, R., Spinrad, J., Tucker, A., Polynomial time recognition of unit circular-arc graphs (2006) J Algorithms, 58, pp. 67-78
  • Golumbic, M., Algorithmic Graph Theory and Perfect Graphs (2004) Annals of Discrete Mathematics, 57. , second edition, North-Holland, Amsterdam
  • Hell, P., Huang, J., Interval bigraphs and circular arc graphs (2004) J Graph Theory, 46 (4), pp. 313-327
  • Lekkerkerker, C., Boland, D., Representation of finite graphs by a set of intervals on the real line (1962) Fund Math, 51, pp. 45-64
  • Lin, M., Szwarcfiter, J., Efficient construction of unit circular-arc models (2006) Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 309-315. , Miami, FL
  • McConnell, R., Linear-time recognition of circular-arc graphs (2003) Algorithmica, 37 (2), pp. 93-147
  • Olariu, S., Paw-free graphs (1988) Inf Process Lett, 28, pp. 53-54
  • Parthasarathy, K., Ravindra, G., The strong perfect-graph conjecture is true for K1,3-free graphs (1976) J Combin Theory Ser B, 21, pp. 212-223
  • Seinsche, D., On a property of the class of w-colorable graphs (1974) J Combin Theory Ser B, 16, pp. 191-193
  • Trotter, W., Moore, J., Characterization problems for graphs, partially ordered sets, lattices, and families of sets (1976) Discrete Math, 16, pp. 361-381
  • Tucker, A., Structure theorems for some circular-arc graphs (1974) Discrete Math, 7, pp. 167-195
  • Tucker, A., Coloring perfect (K4 - e)-free graphs (1987) J Combin Theory Ser B, 42, pp. 313-318

Citas:

---------- APA ----------
Bonomo, F., Durán, G., Grippo, L.N. & Safe, M.D. (2009) . Partial characterizations of circular-arc graphs. Journal of Graph Theory, 61(4), 289-306.
http://dx.doi.org/10.1002/jgt.20379
---------- CHICAGO ----------
Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D. "Partial characterizations of circular-arc graphs" . Journal of Graph Theory 61, no. 4 (2009) : 289-306.
http://dx.doi.org/10.1002/jgt.20379
---------- MLA ----------
Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D. "Partial characterizations of circular-arc graphs" . Journal of Graph Theory, vol. 61, no. 4, 2009, pp. 289-306.
http://dx.doi.org/10.1002/jgt.20379
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D. Partial characterizations of circular-arc graphs. J. Graph Theory. 2009;61(4):289-306.
http://dx.doi.org/10.1002/jgt.20379