The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
For a given induced hereditary property 𝓟, a 𝓟-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property 𝓟. We consider the effectiveness of on-line 𝓟-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function of any stingy on-line 𝓟-coloring algorithm. In the class of generalized...
We prove that for any two minor hereditary properties 𝓟₁ and 𝓟₂, such that 𝓟₂ covers 𝓟₁, and for any graph G ∈ 𝓟₂ there is a 𝓟₁-bipartition of G. Some remarks on minimal reducible bounds are also included.
A linear forest is a forest in which every component is a path. It is known that the set of vertices V(G) of any outerplanar graph G can be partitioned into two disjoint subsets V₁,V₂ such that induced subgraphs ⟨V₁⟩ and ⟨V₂⟩ are linear forests (we say G has an (LF, LF)-partition). In this paper, we present an extension of the above result to the class of planar graphs with a given number of internal vertices (i.e., vertices that do not belong to the external face at a certain fixed embedding of...
A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T),...
A graph is a if for any vertex the subgraph induced by the neighbours of is a -tree, , where -tree is an edgeless graph, -tree is a tree. We characterize the minimum-size locally -trees with vertices. The minimum-size connected locally -trees are simply -trees. For , we construct locally -trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an -vertex locally -tree graph is between and , where both bounds are asymptotically...
Download Results (CSV)