Name
Abstract | ||
|---|---|---|
Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number chi(t)(G) is the least integer k for which G admits a coloring with k colors such that each color class induces a (t - 1)-degenerate subgraph of G. So chi(1) is the chromatic number and chi(2) is the point arboricity. The point partition number chi(t) with t >= 1 was introduced by Lick and White. A graph G is called chi(t)-critical if every proper subgraph H of G satisfies chi H-t() < chi(t)(G). In this paper we prove that if G is a chi(t)-critical graph whose order satisfies |G| <= 2 chi(t)(G) - 2, then G can be obtained from two non-empty disjoint subgraphs G(1 )and G(2) by adding t edges between any pair u, v of vertices with u is an element of V(G(1)) and v <= V(G(2)). Based on this result we establish the minimum number of edges possible in a chi(t)-critical graph G of order n and with chi(t)(G) = k, provided that n <= 2k - 1 and t is even. For t =1 the corresponding two results were obtained in 1963 by Tibor Gallai. (C)& nbsp;2022 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.disc.2022.112903 | DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
Graph coloring, Point partition numbers, Critical graphs, Dirac join | Journal | 345 |
Issue | ISSN | Citations |
8 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| von Postel Justus | 1 | 0 | 0.34 |
| Schweser Thomas | 2 | 0 | 0.34 |
| Michael Stiebitz | 3 | 207 | 30.08 |