Pattern　recognition　algorithms　are　facing　the　challenge　to　deal　with　an　increasing　number　of　complex　objects.　For　graph　data,　a　whole　toolbox　of　pattern　recognition　algorithms　becomes　available　by　defining　a　kernel　function　on　instances　of　graphs.　Graph　similarity　is　the　central　problem　for　all　learning　tasks　such　as　clustering　and　classification　on　graphs.　Graph　kernels　based　on　walks,　shortest　path,　subtrees　and　cycles　in　graphs　have　been　proposed　so　far.　As　a　general　problem,　these　kernels　are　either　computationally　expensive　or　limited　in　their　expressiveness.　We　try　to　overcome　this　problem　by　defining　expressive　graph　kernels　which　are　based　on　diconnected　components　(dicomponent)　of　directed　graph.　Dicomponents　kernel　of　directed　graph　(digraph)　is　computable　in　polynomial　time,　retain　expressivity　and　are　still　positive　definite.　In　experiments　on　classification　of　graph　models　of　face　images,　our　dicomponents　kernel　of　digraph　show　significantly　higher　classification　accuracy.　©　2010　IEEE.