Perfect graphs with polynomially computable kernels

DOI10.1016/j.dam.2018.09.027zbMath1429.05079arXiv1801.02253OpenAlexW2964139924WikidataQ128983564 ScholiaQ128983564MaRDI QIDQ2283107

Adèle Pass-Lanneau, Ayumi Igarashi, Frédéric Meunier

Publication date: 30 December 2019

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

Full work available at URL: https://arxiv.org/abs/1801.02253

zbMATH Keywords

kernelchordal graphclique-cutsetBoros-Gurvich theoremclaw-free perfect graphorientation of perfect graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Perfect graphs (05C17)

Related Items (1)

On the kernel and related problems in interval digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
• Polynomial algorithms for kernels in comparability, permutation and \(P_4\)-free graphs
• Kernels in perfect line-graphs
• A note on kernels and Sperner's Lemma
• Decomposition by clique separators
• Intersection graphs of paths in a tree
• Recognizing claw-free perfect graphs
• Perfect graphs are kernel solvable
• Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
• A description of claw-free perfect graphs
• Fractional kernels in digraphs
• On kernels in i-triangulated graphs
• The list chromatic index of a bipartite multigraph
• Kernels in graphs with a clique-cutset
• Perfect graphs, kernels, and cores of cooperative games
• Reducibility among Fractional Stability Problems
• Perfect Digraphs
• Stable marriage assignment for unequal sets
• On weakly ordered systems
• College Admissions and the Stability of Marriage

This page was built for publication: Perfect graphs with polynomially computable kernels