A characterization of normal fraternally orientable perfect graphs (Q1357743): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: In-tournament digraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4099676 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recent problems and results about kernels in directed graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Chordless Paths, Odd Holes, and Kernels in Graphs Without m-Obstructions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An algorithm for fraternal orientation of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5184934 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Triangulated graphs and the elimination process / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs / rank | |||
Normal rank |
Latest revision as of 16:41, 27 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A characterization of normal fraternally orientable perfect graphs |
scientific article |
Statements
A characterization of normal fraternally orientable perfect graphs (English)
0 references
1 April 1998
0 references
A digraph \(D= (V(D),A(D))\) is called a fraternal orientation of a graph \(G\) if \(u\to w\), \(v\to w\in A(D)\) implies that at least one of the arcs \(u\to v\), \(v\to u\) is in \(A(D)\). This definition is somewhat misleading since we normally do not allow directed cycles of length 2 in orientations of graphs. Another, in the reviewer's opinion, better name for such a digraph is the term in-semicomplete: it is easy to see that if \(D\) satisfies the condition above, then for every vertex \(v\in V(D)\) the set of in-neighbours of \(v\) induce a semicomplete digraph (i.e., a digraph with no pair of nonadjacent vertices). A kernel of a digraph \(D\) is a set of vertices which satisfies: (i) The digraph induced by \(X\) has no arcs. (ii) For every \(z\in V(D)\backslash X\) there exists \(x\in X\) such that \(z\to x\) is an arc of \(D\). A digraph \(D\) is kernel-perfect if every induced subgraph of \(D\) has a kernel. It is easy to see that every semicomplete induced subgraph of a kernel-perfect digraph must have an absorbing vertex (i.e., a vertex which is an out-neighbour of every other vertex). A digraph \(D_G\) is called a normal orientation of \(G\) if every semisimple induced subgraph of \(D\) has an absorbing vertex. A conjecture of Berge and Duchet states that a graph \(G\) is perfect if and only if every normal orientation of \(G\) is kernel-perfect. In this paper, the author proves a variant of this conjecture for the case when \(G\) allows a normal fraternal orientation.
0 references
digraph
0 references
fraternal orientation
0 references
kernel
0 references
kernel-perfect digraph
0 references
normal orientation
0 references