Abstract | ||
---|---|---|
For any set S of positive integers, a mixed hypergraph H is a realization of S if its feasible set is S, furthermore, H is a one-realization of S if it is a realization of S and each entry of its chromatic spectrum is either 0 or 1. Jiang et al. showed that the minimum number of vertices of a realization of {s, t} with 2 <= s <= t - 2 is 2t - s. Kral proved that there exists a one-realization of S with at most vertical bar S vertical bar + 2 max S - min S vertices. In this paper, we determine the number of vertices of the smallest one-realization of a given set. As a result, we partially solve an open problem proposed by Jiang et al. in 2002 and by Kral in 2004. |
Year | DOI | Venue |
---|---|---|
2012 | null | ELECTRONIC JOURNAL OF COMBINATORICS |
Keywords | Field | DocType |
hypergraph coloring,mixed hypergraph,feasible set,chromatic spectrum,one-realization | Integer,Discrete mathematics,Combinatorics,Finite set,Chromatic scale,Vertex (geometry),Hypergraph,Feasible region,Mathematics | Journal |
Volume | Issue | ISSN |
19.0 | 1.0 | 1077-8926 |
Citations | PageRank | References |
7 | 0.56 | 0 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ping Zhao | 1 | 40 | 2.39 |
Kefeng Diao | 2 | 36 | 5.29 |
Kaishun Wang | 3 | 227 | 39.82 |