Name
Abstract | ||
|---|---|---|
For a graph G, let chi(G) and lambda(G) denote the chromatic number of G and the maximum local edge connectivity of G, respectively. A result of Dirac implies that every graph G satisfies chi(G) <= lambda(G) + 1. In this paper we characterize the graphs G for which chi(G) = lambda(G) + 1. The case lambda(G) = 3 was already solved by Aboulker, Brettell, Havet, Marx, and Trotignon. We show that a graph G with lambda(G) = k >= 4 satisfies chi(G) = k +1 if and only if G contains a block which can be obtained from copies of Kk+1 by repeated applications of the Hajos join. |
Year | Venue | Keywords |
|---|---|---|
2018 | ELECTRONIC JOURNAL OF COMBINATORICS | graph coloring,connectivity,critical graphs,Brooks' theorem |
Field | DocType | Volume |
Discrete mathematics,Graph,Combinatorics,Dirac (video compression format),Mathematics | Journal | 25 |
Issue | ISSN | Citations |
1 | 1077-8926 | 0 |
PageRank | References | Authors |
0.34 | 1 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Stiebitz | 1 | 207 | 30.08 |
| Bjarne Toft | 2 | 195 | 51.79 |