Name
Abstract | ||
|---|---|---|
In the study of graph edge coloring for simple graphs, a graph G is called Δ-critical if Δ(G)=Δ, χ′(G)=Δ(G)+1 and χ′(H)<χ′(G) for every proper subgraph H of G. In this paper, we prove a new adjacency result of critical graphs which allows us to control the degree of vertices with distance four. Combining this result with a previous theorem proved by the authors, we show that for every ϵ>0, if G is a Δ-critical graph with order n, then the average degree d‾(G)≥(1−ϵ)Δ and the independence number α(G)≤(12+ϵ)n provided Δ is sufficiently large. This shows that, for a Δ-critical graph G, d‾(G)≥Δ−o(Δ) and α(G)≤(1/2+o(1))n as Δ→∞. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.jctb.2020.07.007 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Chromatic index,Δ-critical graph,Average degree,Independence number | Journal | 145 |
ISSN | Citations | PageRank |
0095-8956 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yan Cao | 1 | 14 | 4.30 |
| Guantao Chen | 2 | 107 | 25.00 |