Name
Abstract | ||
|---|---|---|
Let k be a positive integer at least 2. A graph is k-critical if it can be colored in no fewer than k colors and its proper subgraphs can be colored in fewer than k colors. T. Gallai asked whether a k-critical graph on n vertices contains n distinct (k−1)-critical subgraphs. This paper gives an affirmative answer to Gallai's question restricted to 4-critical graphs by proving they contain at least 83n−293 odd cycles. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.jctb.2019.03.003 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Nonbipartite graph,4-critical graph,Cyclomatic number,Ear decomposition | Journal | 139 |
ISSN | Citations | PageRank |
0095-8956 | 0 | 0.34 |
References | Authors | |
0 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Donovan R. Hare | 1 | 0 | 0.34 |