“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 2338 |
|
||||
| Abstract: | |||||
|
This paper proves that every (n + 1)-chromatic graph contains a
subgraph H with χc (H) = n . This provides easy methods
for constructing sparse graphs G with χc (G) = χ(G) = n. It is also proved that for any ε > 0, for any
fraction k/d > 2, there exsits an integer g such that if G
has girth at least g and χc (G) = k / d then for every
vertex υ of G, χc(G− υ) > k / d − ϵ. This implies that G has an induced
subgraph H with χc(G) − ϵ < χc (H) < χc(G).
Download TeX format |
|||||
| back to top | |||||
