No label defined (Q3688409)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3910416
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3910416

      Statements

      1984
      0 references
      Strong Perfect Graph Conjecture
      0 references
      circle graph
      0 references
      SPGC
      0 references
      [For the entire collection see Zbl 0549.00001.] The Strong Perfect Graph Conjecture states that a graph G is perfect (i.e. the chromatic number of any induced subgraph H equals the size of the largest clique in H) if and only if neither G nor its complement contains a cycle of odd length without diagonals. A circle graph is a graph whose vertices may be put into one-to-one correspondence with the chords of a circle, such that two vertices are adjacent if and only if their corresponding chords intersect. ''In this work we will prove the SPGC is true for the class of circle graphs.'' An alternative proof is to be found in the first author's doctoral thesis (New York University, 1981; Courant Computer Science Report No.21, October, 1980).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references