No label defined (Q3222219)

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 3887724
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3887724

      Statements

      1984
      0 references
      strong perfect graph conjecture
      0 references
      toroidal graphs
      0 references
      [For the entire collection see Zbl 0546.00006.] A graph G is perfect if for each (vertex-induced) subgraph H\b{c}G, the chromatic number of H equals the size of the largest clique in H. The strong perfect graph conjecture due to C. Berge, states that a graph is perfect if and only if neither G nor its complement \(\bar G\) contain an odd hole (an odd hole is an odd chordless cycle of length at least five). This article shows that the strong perfect graph conjecture is valid for toroidal graphs, graphs that can be embedded on the surface of a torus. The proof relies on the fact that one can assume that if the largest clique is \(\geq\) then the toroidal graph is regular of degree six and triangulates the torus.
      0 references

      Identifiers