Navegar

Colección

Datos Estadísticas

Artículo

Bonomo, F.; Durán, G.; Grippo, L.N.; Safe, M.D. "Partial Characterizations of Circular-Arc Graphs" (2008) Electronic Notes in Discrete Mathematics. 30(C):45-50
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
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 subgraphs when the graph belongs to the following classes: diamond-free graphs, P4-free graphs, paw-free graphs, and claw-free chordal graphs. © 2008 Elsevier B.V. All rights reserved.

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, Departamento de Computación, FCEyN, Buenos Aires, Argentina
Departamento de Ingeniería Industrial, FCFM, U. de Chile, Santiago, Chile
Palabras clave:circular-arc graphs; claw-free chordal; cographs; diamond-free graphs; paw-free graphs
Año:2008
Volumen:30
Número:C
Página de inicio:45
Página de fin:50
DOI: http://dx.doi.org/10.1016/j.endm.2008.01.009
Título revista:Electronic Notes in Discrete Mathematics
Título revista abreviado:Electron. Notes Discrete Math.
ISSN:15710653
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v30_nC_p45_Bonomo

Referencias:

  • Bang-Jensen, J., Hell, P., On chordal proper circular arc graphs (1994) Discrete Math., 128, pp. 395-398
  • 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
  • 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) Proc. 17th SODA, pp. 309-315
  • McConnell, R., Linear-time recognition of circular-arc graphs (2003) Algorithmica, 37, pp. 93-147
  • 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

Citas:

---------- APA ----------
Bonomo, F., Durán, G., Grippo, L.N. & Safe, M.D. (2008) . Partial Characterizations of Circular-Arc Graphs. Electronic Notes in Discrete Mathematics, 30(C), 45-50.
http://dx.doi.org/10.1016/j.endm.2008.01.009
---------- CHICAGO ----------
Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D. "Partial Characterizations of Circular-Arc Graphs" . Electronic Notes in Discrete Mathematics 30, no. C (2008) : 45-50.
http://dx.doi.org/10.1016/j.endm.2008.01.009
---------- MLA ----------
Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D. "Partial Characterizations of Circular-Arc Graphs" . Electronic Notes in Discrete Mathematics, vol. 30, no. C, 2008, pp. 45-50.
http://dx.doi.org/10.1016/j.endm.2008.01.009
---------- VANCOUVER ----------
Bonomo, F., Durán, G., Grippo, L.N., Safe, M.D. Partial Characterizations of Circular-Arc Graphs. Electron. Notes Discrete Math. 2008;30(C):45-50.
http://dx.doi.org/10.1016/j.endm.2008.01.009