Maximum set of edges no two covered by a clique (Q1084407)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Maximum set of edges no two covered by a clique |
scientific article; zbMATH DE number 3979091
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Maximum set of edges no two covered by a clique |
scientific article; zbMATH DE number 3979091 |
Statements
Maximum set of edges no two covered by a clique (English)
0 references
1985
0 references
Let h(G) be the largest number of edges of the graph G, no two of which are contained in the same clique. For G without isolated vertices it is proved that if \(h(G)\leq 5\), then \(\chi(\bar G)\leq h(G)\), but if \(h(G)=6\) then \(\chi(G)\) can be arbitrarily large, where \(\bar G\) is the complement of the graph G and \(\chi(\bar G)\) is its chromatic number.
0 references
clique
0 references
chromatic number
0 references
0.7840109467506409
0 references
0.7835063934326172
0 references
0.7622687816619873
0 references
0.7545047998428345
0 references