Article ID Journal Published Year Pages File Type
4657394 Journal of Combinatorial Theory, Series B 2006 20 Pages PDF
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