Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4657394 | Journal of Combinatorial Theory, Series B | 2006 | 20 Pages |
Abstract
A finite, undirected graph is called locally connected, if the neighborhood of every vertex induces a connected subgraph. In this paper we study the existence of edges in locally connected k-connected graphs whose contraction keeps the graph locally connected k-connected.As an application, we prove that the statement of the famous cycle double cover conjecture is true for locally connected graphs.Moreover, we prove that a conjecture of Plummer and Toft on cyclic colorings of 3-connected planar graphs holds when restricted to locally connected graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics