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