Search

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]

Let G be a simple graph with no isolated edges. The neighbor-distinguishing edge coloring of G is a proper edge coloring of G such that any pair of adjacent vertices have different sets consisting of colors assigned on their incident edges. The neighbor-distinguishing index of G , denoted by χ a ′ (G) , is the minimum number of colors in such an edge coloring of G . In this paper, we show that if G is a connected planar graph with maximum degree Δ ≥ 14 , then Δ ≤ χ a ′ (G) ≤ Δ + 1 , and χ a ′ (G) = Δ + 1 if and only if G contains a pair of adjacent vertices of maximum degree. This improves a result in [W. Wang, D. Huang, A characterization on the adjacent vertex distinguishing index of planar graphs with large maximum degree, SIAM J. Discrete Math. 29(2015), 2412–2431], which says that every connected planar graph G with Δ ≥ 16 has Δ ≤ χ a ′ (G) ≤ Δ + 1 , and χ a ′ (G) = Δ + 1 if and only if G contains a pair of adjacent vertices of maximum degree. [ABSTRACT FROM AUTHOR]