An algorithm for fraternal orientation of graphs

DOI10.1016/0020-0190(92)90171-QzbMath0764.68135MaRDI QIDQ1197981

Jorge Urrutia, Fanica Gavril

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

chordal graphs; intersection graphs; fraternal orientation; polynomial time algorithme

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C75: Structural characterization of families of graphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Intersection graphs of proper subtrees of unicyclic graphs, Intersection graphs of concatenable subtrees of graphs, A characterization of normal fraternally orientable perfect graphs, \(B_ 1\)- and \(B_ 2\)-orientable graphs in kernel theory, Grad and classes with bounded expansion. I: Decompositions, Perfect graphs, kernels, and cores of cooperative games

Cites Work

• Intersection graphs of paths in a tree
• Normal fraternally orientable graphs satisfy the strong perfect graph conjecture
• \(B_ 1\)- and \(B_ 2\)-orientable graphs in kernel theory
• Triangulated graphs and the elimination process
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs