Abstract | ||
---|---|---|
A k-stable set in a graph is a stable set of size at most k. We study the convex hull of the k-stable sets of a graph, aiming for a complete inequality description. We also consider colorings of weighted graphs by k-stable sets, aiming for a relation between the values of an optimal coloring and an optimal fractional coloring. Results for k=2 and k=3 as well as a number of general conjectures linking fractional and integral colorings are given. |
Year | DOI | Venue |
---|---|---|
1999 | 10.1137/S089548019630978X | SIAM J. Discrete Math. |
Keywords | Field | DocType |
convex hull,weighted graph,optimal coloring,general conjecture,integral colorings,k-stable set,bounded stable sets,stable set,optimal fractional coloring,complete inequality description | Graph theory,Edge coloring,Discrete mathematics,Complete coloring,Combinatorics,Fractional coloring,Convex hull,Independent set,Polytope,Greedy coloring,Mathematics | Journal |
Volume | Issue | ISSN |
12 | 2 | 0895-4801 |
Citations | PageRank | References |
2 | 0.38 | 3 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jeannette Janssen | 1 | 295 | 32.23 |
Kyriakos Kilakos | 2 | 21 | 3.97 |