Name
Abstract | ||
|---|---|---|
A graph G is chromatically k-connected if every vertex cutset induces a subgraph with chromatic number at least k. Thus, in particular each neighborhood has to induce ak-chromatic subgraph. Godsil, Nowakowski and Nesetril asked whether there exists ak-chromatically connected graph such that every minimal cutset induces a subgraph with no triangles. We show that the answer is positive in a special case, when minimal is replaced by minimum cutsets. We will also answer another related question suggested by Nesetril by proving the existence of highly chromatically connected graphs in which every vertex neighborhood induces a subgraph with a given girth. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.disc.2008.03.023 | Discrete Mathematics |
Keywords | Field | DocType |
kneser graphs,chromatic connectivity,connected graph | Discrete mathematics,Combinatorics,Chromatic scale,Vertex (geometry),Existential quantification,Vertex (graph theory),Induced subgraph isomorphism problem,Connectivity,Subgraph isomorphism problem,Mathematics,Special case | Journal |
Volume | Issue | ISSN |
309 | 18 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrzej Dudek | 1 | 114 | 23.10 |
| E. Năstase | 2 | 12 | 2.92 |
| Vojtěch Rödl | 3 | 887 | 142.68 |