It also appears that you are not passing in your color map in main.cpp yes and in this case it should be created internally by the dfs function.

If your graph has a vertex_index_map property map (filled in appropriately) If I use bundle properties is there an automatic vertex_index_map ?

It's not just to initialize the color map, but to use it during the algorithm as well. ok

Could you please send your full error trace? Exactly the same code works with vecS.

In file included from /usr/include/c++/4.4/backward/hash_set:59, from .../extern/boost/boost/pending/container_traits.hpp:23, from .../extern/boost/boost/graph/detail/adjacency_list.hpp:31, from .../extern/boost/boost/graph/adjacency_list.hpp:324, from applications/testGraph/src/main.cpp:3: /usr/include/c++/4.4/backward/backward_warning.h:28:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated. In file included from .../extern/boost/boost/graph/named_function_params.hpp:23, from .../extern/boost/boost/graph/depth_first_search.hpp:22, from applications/testGraph/src/main.cpp:5: .../extern/boost/boost/property_map/shared_array_property_map.hpp: In member function 'T& boost::shared_array_property_map<T, IndexMap>::operator[](typename boost::property_traits<IndexMap>::key_type) const [with T = boost::default_color_type, IndexMap = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, Vertex, Edge, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>]': .../extern/boost/boost/property_map/property_map.hpp:325: instantiated from 'void boost::put(const boost::put_get_helper<Reference, PropertyMap>&, K, const V&) [with PropertyMap = boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, Vertex, Edge, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t> >, Reference = boost::default_color_type&, K = void*, V = boost::default_color_type]' .../extern/boost/boost/graph/depth_first_search.hpp:197: instantiated from 'void boost::depth_first_search(const VertexListGraph&, DFSVisitor, ColorMap, typename boost::graph_traits<Graph>::vertex_descriptor) [with VertexListGraph = boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, Vertex, Edge, boost::no_property, boost::listS>, DFSVisitor = CycleDetector, ColorMap = boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, Vertex, Edge, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t> >]' .../extern/boost/boost/graph/depth_first_search.hpp:297: instantiated from 'void boost::depth_first_search(const VertexListGraph&, const boost::bgl_named_params<P, T, R>&) [with VertexListGraph = GraphContainer, P = CycleDetector, T = boost::graph_visitor_t, R = boost::no_property]' applications/testGraph/src/main.cpp:77: instantiated from here .../extern/boost/boost/property_map/shared_array_property_map.hpp:36: error: no match for 'operator[]' in '((const boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, Vertex, Edge, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t> >*)this)->boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, Vertex, Edge, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t> >::data[boost::get [with PropertyMap = boost::adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, Vertex, Edge, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t>, Reference = const boost::detail::error_property_not_found&, K = void*](((const boost::put_get_helper<const boost::detail::error_property_not_found&, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, Vertex, Edge, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t> >&)((const boost::put_get_helper<const boost::detail::error_property_not_found&, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, Vertex, Edge, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t> >*)(&((const boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, Vertex, Edge, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t> >*)this)->boost::shared_array_property_map<boost::default_color_type, boost::adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, Vertex, Edge, boost::no_property, boost::listS>, boost::detail::error_property_not_found, const boost::detail::error_property_not_found&, boost::vertex_index_t> >::index))), ((void* const&)((void* const*)(& v))))]' .../extern/boost/boost/smart_ptr/shared_array.hpp:85: note: candidates are: T& boost::shared_array<T>::operator[](ptrdiff_t) const [with T = boost::default_color_type]