Search

In this paper we use the classical notion of weak Mycielskian M′(G) of a graph G and the following sequence: M′0(G) = G, M′1(G) = M′(G), and M′n(G) = M′(M′n−1(G)), to show that if G is a complete graph of order p, then the above sequence is a generator of the class of p-colorable graphs. Similarly, using Mycielskian M(G) we show that analogously defined sequence is a generator of the class consisting of graphs for which the chromatic number of the subgraph induced by all vertices that belong to at least one triangle is at most p. We also address the problem of characterizing the latter class in terms of forbidden graphs.

Given a hypergraph 𝒣 and a function f : V (𝒣) → 𝕅, we say that 𝒣 is f-choosable if there is a proper vertex colouring ϕ of 𝒣 such that ϕ (v) ∈ L(v) for all v ∈ V (𝒣), where L : V (𝒣) → 2𝕅 is any assignment of f(v) colours to a vertex v. The sum choice number 𝒣isc(𝒣) of 𝒣 is defined to be the minimum of Σv∈V(𝒣)f(v) over all functions f such that 𝒣 is f-choosable. For an arbitrary hypergraph 𝒣 the inequality χsc(𝒣) ≤ |V (𝒣)| + |ɛ (𝒣)| holds, and hypergraphs that attain this upper bound are called sc-greedy. In this paper we characterize sc-greedy hypergraphs that are unions of a hypercycle and a hyperpath having at most two vertices in common. Consequently, we characterize the hypergraphs of this type that are forbidden for the class of sc-greedy hypergraphs.

Let 𝒫 be an arbitrary class of graphs that is closed under taking induced subgraphs and let 𝒞 (𝒫) be the family of forbidden subgraphs for 𝒫. We investigate the class 𝒫 (k) consisting of all the graphs G for which the removal of no more than k vertices results in graphs that belong to 𝒫. This approach provides an analogy to apex graphs and apex-outerplanar graphs studied previously. We give a sharp upper bound on the number of vertices of graphs in 𝒞 (𝒫 (1)) and we give a construction of graphs in 𝒞 (𝒫 (k)) of relatively large order for k ≥ 2. This construction implies a lower bound on the maximum order of graphs in 𝒞 (𝒫 (k)). Especially, we investigate 𝒞 (𝒲r(1)), where 𝒲r denotes the class of Pr-free graphs. We determine some forbidden subgraphs for the class 𝒲r(1) with the minimum and maximum number of vertices. Moreover, we give sufficient conditions for graphs belonging to 𝒞(𝒫 (k)), where 𝒫 is an additive class, and a characterisation of all forests in C(𝒫 (k)). Particularly we deal with 𝒞(𝒫 (1)), where 𝒫 is a class closed under substitution and obtain a characterisation of all graphs in the corresponding 𝒞(𝒫 (1)). In order to obtain desired results we exploit some hypergraph tools and this technique gives a new result in the hypergraph theory.

A problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well as handle any vertex recoloring requests. Our main concern is the greedy approach and characterization of graph classes for which it is possible to decide in polynomial time whether for the fixed forbidden graph F and positive integer k the greedy algorithm ever uses more than k colors in dynamic F-free coloring. For various classes of graphs we give such characterizations in terms of a finite number of minimal forbidden graphs thus solving the above-mentioned problem for the so-called F-trees when F is 2-connected, and for classical trees, when F is a path of order 3 (the latter variant is also known as subcoloring or 1-improper coloring). [ABSTRACT FROM AUTHOR]

A k-coloring (not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k-colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5-coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2-coloring in which each color class induces a graph with maximum degree at most 3 is NP-complete, even for graphs with maximum degree 5. We also give a linear-time algorithm for an acyclic t-improper coloring of any graph with maximum degree d assuming that the number of colors is large enough. [ABSTRACT FROM AUTHOR]