Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A circle graph is the intersection graph of a family of chords on a circle. There is no known characterization of circle graphs by forbidden induced subgraphs that do not involve the notions of local equivalence or pivoting operations. We characterize circle graphs by a list of minimal forbidden induced subgraphs when the graph belongs to one of the following classes: linear domino graphs, P4-tidy graphs, and tree-cographs. We also completely characterize by minimal forbidden induced subgraphs the class of unit Helly circle graphs, which are those circle graphs having a model whose chords have all the same length, are pairwise different, and satisfy the Helly property. © 2010 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Partial characterizations of circle graphs
Autor:Bonomo, F.; Durán, G.; Grippo, L.N.; Safe, M.D.
Filiación:CONICET, Argentina
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile
Instituto de Ciencias, Universidad Nacional de General Sarmiento, Los Polvorines, Argentina
Palabras clave:P 4-tidy graphs; Circle graphs; Helly circle graphs; Linear domino graphs; Tree-cographs; Unit circle graphs; P 4-tidy graphs; Circle graphs; Helly circle graphs; Linear domino graphs; Tree-cographs; Unit circles; Graphic methods; Plant extracts; Trees (mathematics)
Año:2011
Volumen:159
Número:16
Página de inicio:1699
Página de fin:1706
DOI: http://dx.doi.org/10.1016/j.dam.2010.06.020
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0166218X_v159_n16_p1699_Bonomo.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v159_n16_p1699_Bonomo

Referencias:

  • Bandelt, H., Mulder, H., Distancehereditary graphs (1986) Journal of Combinatorial Theory. Series B, 41 (2), pp. 182-208
  • Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D., Partial characterizations of circular-arc graphs (2009) Journal of Graph Theory, 61 (4), pp. 289-306
  • Bouchet, A., Reducing prime graphs and recognizing circle graphs (1987) Combinatorica, 7 (3), pp. 243-254
  • Bouchet, A., Circle graphs obstructions (1994) Journal of Combinatorial Theory. Series B, 60 (1), pp. 107-144
  • Brandstdt, A., Le, V.B., Spinrad, J.P., (1999) Graph Classes: A Survey, 3. , SIAM Monographs on Discrete Mathematics SIAM Philadelphia
  • Chudnovsky, M., Kapadia, R., Detecting a theta or a prism (2008) SIAM Journal on Discrete Mathematics, 22 (3), pp. 1164-1186
  • Cunningham, W.H., Decomposition of directed graphs (1982) SIAM Journal on Algebraic and Discrete Methods, 3 (2), pp. 214-228
  • Czemerinski, H., Duran, G., Gravano, A., Bouchet Graphs: A Generalization of Circle Graphs (2002) Congressus Numerantium, (155), pp. 95-108
  • Daligault, J., Gonalves, D., Rao, M., Diamond-free circle graphs are Helly circle (2010) Discrete Mathematics, 310 (4), pp. 845-849
  • Durán, G., Some new results on circle graphs (2003) Matemática Contempornea, 25, pp. 91-106
  • Duran, G., Gravano, A., McConnell, R.M., Spinrad, J., Tucker, A., Polynomial time recognition of unit circular-arc graphs (2006) Journal of Algorithms, 58 (1), pp. 67-78. , DOI 10.1016/j.jalgor.2004.08.003, PII S0196677404001464
  • Even, S., Itai, A., Queues, stacks and graphs (1971) Theory of Machines and Computations, pp. 71-86. , Z. Kohavi, A. Paz, Academic Press New York
  • Gallai, T., Transitiv orientierbare Graphen (1967) Acta Mathematica Academiae Scientiarum Hungaricae, 18 (12), pp. 25-66
  • Geelen, J., Oum, S., Circle graph obstructions under pivoting (2009) Journal of Graph Theory, 61 (1), pp. 1-11
  • Giakoumakis, V., Roussel, F., Thuillier, H., On P 4-tidy graphs (1997) Discrete Mathematics & Theoretical Computer Science, 1, pp. 17-41
  • Golumbic, M., (2004) Algorithmic Graph Theory and Perfect Graphs, 57. , second ed. Annals of Discrete Mathematics North-Holland Amsterdam
  • Hong, C.T., (1985) Perfect Graphs, , Ph.D. Thesis, School of Computer Science, McGill University, Montreal
  • Jamison, B., Olariu, S., A new class of brittle graphs (1989) Studies in Applied Mathematics, 81, pp. 89-92
  • Jamison, B., Olariu, S., On a unique tree representation for P 4-extendible graphs (1991) Discrete Applied Mathematics, 34, pp. 151-164
  • Kloks, T., Kratsch, D., Müller, H., Dominoes (1995) Lecture Notes in Computer Science, 903, pp. 106-120
  • Knuth, D.E., (1968) The Art of Computer Programming, 1. , Addison-Wesley Reading, MA
  • Krylou, Y.V., Perez Tchernov, A.J., On the problem of domino recognition (2006) Electronic Notes in Discrete Mathematics, 24, pp. 251-258. , DOI 10.1016/j.endm.2006.06.029, PII S1571065306000412
  • Lévêque, B., Lin, D., Maffray, F., Trotignon, N., Detecting induced subgraphs (2007) Electronic Notes in Discrete Mathematics, 29, pp. 207-211
  • Lin, M.C., Szwarcfiter, J.L., Efficient construction of unit circular-arc models (2006) Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 309-315. , Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
  • Naji, W., Reconnaissance des graphes de cordes (1985) Discrete Mathematics, 54, pp. 329-337
  • Pnueli, A., Lempel, A., Even, S., Transitive orientation of graphs and identification of permutation graphs (1971) Canadian Journal of Mathematics, 23, pp. 160-175
  • Seinsche, D., On a property of the class of n-colorable graphs (1974) Journal of Combinatorial Theory. Series B, 16 (2), pp. 191-193
  • Spinrad, J., Recognition of circle graphs (1994) Journal of Algorithms, 16 (2), pp. 264-282
  • Tinhofer, G., Strong tree-cographs are Birkoff graphs (1989) Discrete Applied Mathematics, 22 (3), pp. 275-288
  • Tucker, A., Structure theorems for some circular-arc graphs (1974) Discrete Mathematics, 7, pp. 167-195

Citas:

---------- APA ----------
Bonomo, F., Durán, G., Grippo, L.N. & Safe, M.D. (2011) . Partial characterizations of circle graphs. Discrete Applied Mathematics, 159(16), 1699-1706.
http://dx.doi.org/10.1016/j.dam.2010.06.020
---------- CHICAGO ----------
Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D. "Partial characterizations of circle graphs" . Discrete Applied Mathematics 159, no. 16 (2011) : 1699-1706.
http://dx.doi.org/10.1016/j.dam.2010.06.020
---------- MLA ----------
Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D. "Partial characterizations of circle graphs" . Discrete Applied Mathematics, vol. 159, no. 16, 2011, pp. 1699-1706.
http://dx.doi.org/10.1016/j.dam.2010.06.020
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D. Partial characterizations of circle graphs. Discrete Appl Math. 2011;159(16):1699-1706.
http://dx.doi.org/10.1016/j.dam.2010.06.020