Circular-arc graphs are the intersection graphs of open arcs on a circle. Circle graphs are the intersection graphs of chords on a circle. These graph classes have been the subject of much study for many years and numerous interesting results have been reported. Many subclasses of both circular-arc graphs and circle graphs have been defined and different characterizations formulated. In this survey, we summarize the most important structural results related to circular-arc graphs and circle graphs and present the main open problems. © 2013.
Documento: | Artículo |
Título: | Structural results on circular-arc graphs and circle graphs: A survey and the main open problems |
Autor: | Durán, G.; Grippo, L.N.; Safe, M.D. |
Filiación: | CONICET, Argentina Departamento de Matemática and Instituto de Cálculo, 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 |
Idioma: | Inglés |
Palabras clave: | Circle graphs; Circular-arc graphs; Forbidden subgraph characterizations; Interval graphs; Matrix characterizations; Permutation graphs |
Año: | 2013 |
DOI: | http://dx.doi.org/10.1016/j.dam.2012.12.021 |
Título revista: | Discrete Applied Mathematics |
Título revista abreviado: | Discrete Appl Math |
ISSN: | 0166218X |
CODEN: | DAMAD |
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v_n_p_Duran |