کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648149 | 1342394 | 2012 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A new characterization of perfect graphs A new characterization of perfect graphs](/preview/png/4648149.png)
Let D=(V(D),A(D))D=(V(D),A(D)) be a digraph; a kernel NN of DD is a set of vertices N⊆V(D)N⊆V(D) such that NN is independent (for any x,y∈Nx,y∈N, there is no arc between them) and NN is absorbent (for each x∈V(D)−Nx∈V(D)−N, there exists an xNxN-arc in DD). A digraph DD is said to be kernel-perfect whenever each one of its induced subdigraphs has a kernel. A digraph DD is oriented by sinks when every semicomplete subdigraph of DD has at least one kernel. Let us recall that a graph GG is perfect iff every induced subdigraph HH satisfies α(H)=θ(H)α(H)=θ(H), where α(G)α(G) denotes the stability number of GG (i.e. the maximum cardinality of an independent set of vertices of GG) and θ(G)θ(G) denotes the minimum number of cliques needed to cover the vertex-set of GG.Let GG be a graph and α=(αu)u∈V(G)α=(αu)u∈V(G) a family of mutually disjoint digraphs; a sum of αα over GG, denoted by σ(α,G)σ(α,G) is a digraph defined as follows. Take ⋃u∈V(G)αu⋃u∈V(G)αu, and then for each x∈V(αw)x∈V(αw) and y∈V(αv)y∈V(αv) with [w,v]∈E(G)[w,v]∈E(G) we put at least one of the two arcs (x,y)(x,y) or (y,x)(y,x) in σ(α,G)σ(α,G).The main result of this paper is the following theorem which provides a new characterization of perfect graphs.Theorem. A graph GGis perfect if and only if for any family α=(αv)v∈V(G)α=(αv)v∈V(G)of mutually disjoint asymmetric kernel-perfect digraphs, any digraph constructed as a sum of ααover GG, σ(α,G)σ(α,G)and oriented by sinks is kernel-perfect.
Journal: Discrete Mathematics - Volume 312, Issue 17, 6 September 2012, Pages 2751–2755