On weakly diamond-free Berge graphs (Q1126205): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Chris Jagger / rank | |||
Property / reviewed by | |||
Property / reviewed by: Chris Jagger / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Coloring perfect degenerate graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3286847 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Coloring perfect \((K_ 4\)-e)-free graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A reduction procedure for coloring perfect \(K_ 4\)-free graphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 16:10, 24 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On weakly diamond-free Berge graphs |
scientific article |
Statements
On weakly diamond-free Berge graphs (English)
0 references
8 December 1996
0 references
A graph is perfect if, for each induced subgraph \(H\), the chromatic number of \(H\) is equal to the maximum clique size \(\omega(H)\) of \(H\). A hole is a chordless cycle of length at least four, and an antihole is the complementary graph of a hole. A graph \(G\) is a Berge graph if \(G\) contains neither an odd hole, nor an odd antihole. The strong perfect graph conjecture says `A graph is perfect iff it is a Berge graph'. A diamond is a \(K_4\) minus an edge. A vertex \(v\) in graph \(G\) is called WDF (weakly diamond-free) if its degree is at most \(2\omega(G)-1\) and its neighbourhood in \(G\) induces a diamond-free subgraph. \(G\) is called WDF if every induced subgraph of \(G\) has a WDF vertex. This class contains chordal graphs and perfect line-graphs. The authors prove the strong perfect graph conjecture for WDF graphs.
0 references
chromatic number
0 references
clique size
0 references
hole
0 references
antihole
0 references
Berge graph
0 references
strong perfect graph conjecture
0 references
diamond
0 references