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]

A proper edge k-colouring of a graph $$G=(V,E)$$ is an assignment $$c:E\rightarrow \{1,2,\ldots ,k\}$$ of colours to the edges of the graph such that no two adjacent edges are associated with the same colour. A neighbour sum distinguishing edge k-colouring, or nsd k-colouring for short, is a proper edge k-colouring such that $$\sum _{e\ni u}c(e)\ne \sum _{e\ni v}c(e)$$ for every edge uv of G. We denote by $$\chi '_{\Sigma }(G)$$ the neighbour sum distinguishing index of G, which is the least integer k such that an nsd k-colouring of G exists. By definition at least maximum degree, $$\Delta (G)$$ colours are needed for this goal. In this paper we prove that $$\chi '_\Sigma (G) \le \Delta (G)+1$$ for any graph G without isolated edges, with $$\mathrm{mad}(G)<3$$ and $$\Delta (G) \ge 6$$ . [ABSTRACT FROM AUTHOR]

A proper edge-coloring of a graph defines at each vertex the set of colors of its incident edges. This set is called the palette of the vertex. In this paper we are interested in the minimum number of palettes taken over all possible proper colorings of a graph. [ABSTRACT FROM AUTHOR]