Partial characterizations of circular-arc graphs
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...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Publicado: |
2009
|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v61_n4_p289_Bonomo http://hdl.handle.net/20.500.12110/paper_03649024_v61_n4_p289_Bonomo |
| Aporte de: |
| Sumario: | 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. |
|---|