Point partition numbers: Decomposable and indecomposable critical graphs |
| |
Affiliation: | Institute of Mathematics, Technische Universität Ilmenau, D-98684 Ilmenau, Germany |
| |
Abstract: | Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number is the least integer k for which G admits a coloring with k colors such that each color class induces a -degenerate subgraph of G. So is the chromatic number and is the point arboricity. The point partition number with was introduced by Lick and White. A graph G is called -critical if every proper subgraph H of G satisfies . In this paper we prove that if G is a -critical graph whose order satisfies , then G can be obtained from two non-empty disjoint subgraphs and by adding t edges between any pair of vertices with and . Based on this result we establish the minimum number of edges possible in a -critical graph G of order n and with , provided that and t is even. For the corresponding two results were obtained in 1963 by Tibor Gallai. |
| |
Keywords: | Graph coloring Point partition numbers Critical graphs Dirac join |
本文献已被 ScienceDirect 等数据库收录! |
|