No label defined (Q3222874)
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 3889564
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3889564 |
Statements
1984
0 references
recognition of parity graphs
0 references
perfect graphs
0 references
polynomial algorithms
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0.8865355
0 references
0.8790723
0 references
[For the entire collection see Zbl 0546.00006.] A parity graph is a graph in which for every pair of vertices (x,y), the lengths of the minimal x,y-paths all have the same parity. The authors characterize these graphs, and observe that they are all perfect graphs. They then discuss polynomial algorithms for recognizing parity graphs, and for determining the maximum stable set, minimum colouring, minimum covering by cliques and maximum clique of a parity graph.
0 references