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.

We say that a graph G is maximal Kp-free if G does not contain Kp but if we add any new edge e ∈ E(G) to G, then the graph G + e contains Kp. We study the minimum and maximum size of non-(p − 1)-partite maximal Kp-free graphs with n vertices. We also answer the interpolation question: for which values of n and m are there any n-vertex maximal Kp-free graphs of size m?

Given a hypergraph H and a function f: V (H) → N, we say that H is f-choosable if there exists a proper vertex colouring φ of H such that φ(v) ∈ L(v) for all v ∈ V (H), where L: V (H) -→ 2N is an assignment of f(v) colours to a vertex v. The sum-choice-number χsc(H) of H is a minimum Σv∈V(H) f(v) taken over all functions f such that H is f-choosable. The hypergraphs for which χsc(H) = |V (H)| + |E(H)| are called sc-greedy. The class of sc-greedy hypergraphs is closed under the union of hypergraphs having at most one vertex in common. In this paper we consider sc-greediness of the union of hypergraphs having two vertices in common. We investigate this operation when one of the arguments is an arbitrary sc-greedy hypergraph while the second one is a hyperpath. Our research is motivated by the possibility of obtaining improved bounds on the sumchoice-number of graphs and new applications to the resource allocation problems in computer systems. [ABSTRACT FROM AUTHOR]

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]