ISSN:
1435-5914
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract A graphG ischromatically k-connected if every vertex cutset induces a subgraph with chromatic number at leastk. This concept arose in some work, involving the third author, on Ramsey Theory. (For the reference, see the text.) Here we begin the study of chromatic connectivity for its own sake. We show thatG is chromaticallyk-connected iff every homomorphic image of it isk-connected. IfG has no triangles then it is at most chromatically 1-connected, but we prove that the Kneser graphs provide examples ofK 4-free graphs with arbitrarily large chromatic connectivity. We also verify thatK 4-free planar graphs are at most chromatically 2-connected.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01864163
