|
|||||
|
|
An Extremal Property of Turán Graphs,II |
|
| Authors: | Spencer N Tofts |
| Institution: | DEPARTMENT OF MATHEMATICS, UNIVERSITY OF PENNSYLVANIA, PHILADELPHIA, PA 19104 |
| Abstract: | Let  denote Turán's graph—the complete 2‐partite graph on n vertices with partition sizes as equal as possible. We show that for all  , the graph  has more proper vertex colorings in at most 4 colors than any other graph with the same number of vertices and edges. |
| Keywords: | Turá n graph extremal graph number of colorings chromatic polynomial Mathematics Subject Classification: 05C15 05C30 05C31 05C35 |