Name
Abstract | ||
|---|---|---|
A graph G is said to satisfy the Vizing bound if chi(G) <= omega(G) + 1, where chi(G) and omega(G) denote the chromatic number and clique number of G, respectively. The class of graphs satisfying the Vizing bound is clearly chi-bounded in the sense of Gyarfas. It has been conjectured that if G is triangle-free and fork-free, where the fork is obtained from K-1,K-4 by subdividing two edges, then G satisfies the Vizing bound. We show that this is true if, in addition, G is C-5-free. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1137/120895834 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
colorings,chi-bounded,Vizing bound | Discrete mathematics,Graph,Combinatorics,Clique number,Chromatic scale,Omega,Mathematics | Journal |
Volume | Issue | ISSN |
28 | 3 | 0895-4801 |
Citations | PageRank | References |
1 | 0.36 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Genghua Fan | 1 | 412 | 65.22 |
| Baogang Xu | 2 | 389 | 37.90 |
| Tianjun Ye | 3 | 1 | 0.36 |
| Xingxing Yu | 4 | 577 | 68.19 |