An algorithm for fraternal orientation of graphs

DOI10.1016/0020-0190(92)90171-QMaRDI QIDQ1197981zbMATH OpenOpenAlexFDO

Authors J. Urrutia, Fanica Gavril

Publication date 16 January 1993

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

Full work available at URL https://doi.org/10.1016/0020-0190(92)90171-q

zbMATH Keywords

intersection graphschordal graphsfraternal orientationpolynomial time algorithme

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Recommendations

• Chordless Paths, Odd Holes, and Kernels in Graphs Without m-Obstructions
• Intersection graphs of concatenable subtrees of graphs
• A characterization of normal fraternally orientable perfect graphs
• Unilateral orientation of mixed graphs
• Intersection graphs of proper subtrees of unicyclic graphs

Cites work

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

Cited in

(14)

• Fraternal augmentations, arrangeability and linear Ramsey numbers
• A characterization of normal fraternally orientable perfect graphs
• Partial characterizations of 1-perfectly orientable graphs
• Generalization of transitive fraternal augmentations for directed graphs and its applications
• Intersection graphs of concatenable subtrees of graphs
• Colouring edges with many colours in cycles
• Grad and classes with bounded expansion. I: Decompositions
• Perfect graphs, kernels, and cores of cooperative games
• Avoidable vertices and edges in graphs: existence, characterization, and applications
• Intersection graphs of proper subtrees of unicyclic graphs
• 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs
• 1-perfectly orientable \(K_{4}\)-minor-free and outerplanar graphs
• \(B_ 1\)- and \(B_ 2\)-orientable graphs in kernel theory
• \(1\)-perfectly orientable graphs and graph products

This page was built for publication: An algorithm for fraternal orientation of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1197981)