2020/03/10 by von Postel, Justus, Schweser, Thomas, Stiebitz, Michael
#05C15 #05C17 #05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2003.04657
Graphs considered in this paper are finite, undirected and without loops, but with multiple edges. For an integer t≥ 1, denote by MGt 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 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. 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 tKn as a subgraph. Let G be a graph belonging to MGt. 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, we give a characterization of χt-perfect graphs of MGt by a set of forbidden induced subgraphs. We also discuss some complexity problems for the class of χt-critical graphs.