Normal fraternally orientable graphs satisfy the strong perfect graph conjecture

DOI10.1016/0012-365X(93)90293-3zbMath0791.05046OpenAlexW2000828143WikidataQ123281560 ScholiaQ123281560MaRDI QIDQ1313857

Hortensia Galeana-Sánchez

Publication date: 3 July 1994

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

Full work available at URL: https://doi.org/10.1016/0012-365x(93)90293-3

zbMATH Keywords

chromatic numberclique numberstrong perfect graph conjecturecolorscomplete subgraphorientable graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items

1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs, Perfect graphs, kernels, and cores of cooperative games, Kernels and perfectness in arc-local tournament digraphs, An algorithm for fraternal orientation of graphs, \(1\)-perfectly orientable graphs and graph products, Partial Characterizations of 1‐Perfectly Orientable Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On kernel-perfect critical digraphs
• A note on kernel-critical graphs
• Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientes
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• Intersection graphs of concatenable subtrees of graphs
• A characterization of normal fraternally orientable perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• Extension Theorems for Solutions of Irreflexive Relations