On regular bipartite-preserving supergraphs.
Let X be a set, κ be a cardinal number and let ℋ be a family of subsets of X which covers each x ∈ X at least κ-fold. What assumptions can ensure that ℋ can be decomposed into κ many disjoint subcovers? We examine this problem under various assumptions on the set X and on the cover ℋ: among other situations, we consider covers of topological spaces by closed sets, interval covers of linearly ordered sets and covers of ℝⁿ by polyhedra and by arbitrary convex sets. We focus on...
A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), where the vertices in one class are colored red and those in the other class are colored blue. Let F be a 2-stratified graph rooted at some blue vertex v. An F-coloring of a graph is a red-blue coloring of the vertices of G in which every blue vertex v belongs to a copy of F rooted at v. The F-domination number is the minimum number of red vertices in an F-coloring of G. In...
In this note we prove that F (2, 2, 4) = 13.
For any graph , let and denote the vertex set and the edge set of respectively. The Boolean function graph of is a graph with vertex set and two vertices in are adjacent if and only if they correspond to two adjacent vertices of , two adjacent edges of or to a vertex and an edge not incident to it in . For brevity, this graph is denoted by . In this paper, structural properties of and its complement including traversability and eccentricity properties are studied. In addition,...
We consider vertex colorings of graphs in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of the coloring is the sum of the costs incurred at each vertex. The cost chromatic number of a graph with respect to a cost set is the minimum number of colors necessary to produce a minimum cost coloring of the graph. We show that the cost chromatic number of maximal outerplanar and maximal planar graphs can be arbitrarily large and construct...