Chromatic number, clique subdivisions, and the conjectures of Hajos and Erdos-Fajtlowicz
For a graph G, let (G) denote its chromatic number and (G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of (G)= (G) over all n-vertex graphs G. A famous conjecture of Haj os from 1961 states that (G) (G) for every graph G. That is, H(n) 1 for all posit...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2012
|
| Online Access: | http://hdl.handle.net/1721.1/71176 |