Recent problems and results about kernels in directed graphs

DOI10.1016/0012-365X(90)90346-JzbMath0721.05027OpenAlexW2016052873MaRDI QIDQ2640613

Pierre Duchet

Publication date: 1990

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(90)90346-j

zbMATH Keywords

directed graphkernel-perfect graphsquasi-perfect graphs

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (05C99) Directed graphs (digraphs), tournaments (05C20)

Related Items (40)

Kernels by monochromatic paths and color-perfect digraphs ⋮ Enumerating the kernels of a directed graph with no odd circuits ⋮ Some results on the structure of kernel-perfect and critical kernel-imperfect digraphs ⋮ H-absorbence and H-independence in 3-quasi-transitive H-coloured digraphs. ⋮ A characterization of normal fraternally orientable perfect graphs ⋮ Combinatorial games on a graph ⋮ A corrected version of the Duchet kernel conjecture ⋮ A circular graph---counterexample to the Duchet kernel conjecture ⋮ Kernels in a special class of digraphs ⋮ On monochromatic paths and monochromatic cycles in edge coloured tournaments ⋮ Infinite kernel perfect digraphs ⋮ A nondeterministic well-founded semantics ⋮ Characterization of asymmetric CKI- and KP-digraphs with covering number at most 3 ⋮ Kernels by rainbow paths in arc-colored tournaments ⋮ On the kernel and related problems in interval digraphs ⋮ Alternating kernels ⋮ Finding kernels or solving SAT ⋮ Independent sets and non-augmentable paths in generalizations of tournaments ⋮ Perfect graphs, kernels, and cores of cooperative games ⋮ Kernels and perfectness in arc-local tournament digraphs ⋮ Experimental investigation of sufficient criteria for relations to have kernels ⋮ A new characterization of perfect graphs ⋮ On the complexity of the 3-kernel problem in some classes of digraphs ⋮ \(H\)-kernels in unions of \(H\)-colored quasi-transitive digraphs ⋮ On panchromatic digraphs and the panchromatic number ⋮ Restricted domination in quasi-transitive and 3-quasi-transitive digraphs ⋮ Graph theoretical structures in logic programs and default theories ⋮ A new generalization of kernels in digraphs ⋮ Kernels by monochromatic paths in digraphs with covering number 2 ⋮ Kernels in planar digraphs ⋮ Kernels and partial line digraphs ⋮ CKI-digraphs, generalized sums and partitions of digraphs ⋮ Strong kernel number in certain oriented cycle extension of graphs ⋮ Stable matching with uncertain pairwise preferences ⋮ Vertex- and edge-minimal and locally minimal graphs ⋮ Miscellaneous Digraph Classes ⋮ Monochromatic paths and at most 2-coloured arc sets in edge-coloured tournaments ⋮ \(H\)-paths and \(H\)-cycles in \(H\)-coloured digraphs ⋮ Closure systems and their structure ⋮ An extension of Richardson's theorem in m-colored digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On kernels in perfect graphs
• On kernels and semikernels of digraphs
• A parity digraph has a kernel
• A note on kernel-critical graphs
• A counterexample to a conjecture of Meyniel on kernel-perfect graphs
• Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientes
• A combinatorial problem in logic
• On kernels in i-triangulated graphs
• Graphes Noyau-Parfaits

This page was built for publication: Recent problems and results about kernels in directed graphs