Back to Search
Start Over
Point Partition Numbers: Perfect Graphs.
- Source :
-
Graphs & Combinatorics . Apr2022, Vol. 38 Issue 2, p1-11. 11p. - Publication Year :
- 2022
-
Abstract
- Graphs considered in this paper are finite, undirected and without loops, but with multiple edges. For an integer t ≥ 1 , denote by MG t the class of graphs whose maximum multiplicity is at most t. A graph G is called strictly t-degenerate if every non-empty subgraph H of G contains a vertex v whose degree in H is at most t - 1 . The point partition number χ t (G) of G is the smallest number of colors needed to color the vertices of G so that each vertex receives a color and vertices with the same color induce a strictly t-degenerate subgraph of G. So χ 1 is the chromatic number, and χ 2 is known as the point aboricity. The point partition number χ t with t ≥ 1 was introduced by Lick and White (Can J Math 22:1082–1096, 1970). If H is a simple graph, then tH denotes the graph obtained from H by replacing each edge of H by t parallel edges. Then ω t (G) is the largest integer n such that G contains a t K n as a subgraph. Let G be a graph belonging to MG t . Then ω t (G) ≤ χ t (G) and we say that G is χ t -perfect if every induced subgraph H of G satisfies ω t (H) = χ t (H) . Based on the Strong Perfect Graph Theorem due to Chudnowsky, Robertson, Seymour and Thomas (Ann Math 164:51–229, 2006), we give a characterization of χ t -perfect graphs of MG t by a set of forbidden induced subgraphs (see Theorems 2 and 3). We also discuss some complexity problems for the class of χ t -critical graphs. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09110119
- Volume :
- 38
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Graphs & Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 154994833
- Full Text :
- https://doi.org/10.1007/s00373-021-02410-w