On the dichromatic number in kernel theory
On the dominator colorings in trees
In a graph G, a vertex is said to dominate itself and all its neighbors. A dominating set of a graph G is a subset of vertices that dominates every vertex of G. The domination number γ(G) is the minimum cardinality of a dominating set of G. A proper coloring of a graph G is a function from the set of vertices of the graph to a set of colors such that any two adjacent vertices have different colors. A dominator coloring of a graph G is a proper coloring such that every vertex of V dominates all vertices...
On the edge coloring of graph products.
On the factorization of reducible properties of graphs into irreducible factors
A hereditary property R of graphs is said to be reducible if there exist hereditary properties P₁,P₂ such that G ∈ R if and only if the set of vertices of G can be partitioned into V(G) = V₁∪V₂ so that ⟨V₁⟩ ∈ P₁ and ⟨V₂⟩ ∈ P₂. The problem of the factorization of reducible properties into irreducible factors is investigated.
On the genus of the complex projective plane.
On the Graph of Large Distances.
On the heterochromatic number of circulant digraphs
The heterochromatic number hc(D) of a digraph D, is the minimum integer k such that for every partition of V(D) into k classes, there is a cyclic triangle whose three vertices belong to different classes. For any two integers s and n with 1 ≤ s ≤ n, let be the oriented graph such that is the set of integers mod 2n+1 and In this paper we prove that for n ≥ 7. The bound is tight since equality holds when s ∈ n,[(2n+1)/3].
On the Independence Number of Edge Chromatic Critical Graphs
In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤ [...] . It is known that α (G) < [...] |V |. In this paper we improve this bound when △≥ 4. Our precise result depends on the number n2 of 2-vertices in G, but in particular we prove that α (G) ≤ [...] |V | when △ ≥ 5 and n2 ≤ 2(△− 1)
On the lower bound for the chromatic number of graphs with given maximal degree and girth.
On the maximum average degree and the incidence chromatic number of a graph.
On the number of Russell’s socks or
The following question is analyzed under the assumption that the Axiom of Choice fails badly: Given a countable number of pairs of socks, then how many socks are there? Surprisingly this number is not uniquely determined by the above information, thus giving rise to the concept of Russell-cardinals. It will be shown that: • some Russell-cardinals are even, but others fail to be so; • no Russell-cardinal is odd; • no Russell-cardinal is comparable with any cardinal of the form or ; • finite sums...
On the oriented game chromatic number.
On the possibility of applying a computer when solving the four color problem
On the pseudoachromatic number of a graph
On the quantum chromatic number of a graph.
On the rainbow connection of Cartesian products and their subgraphs
Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and non-existence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded above by the rainbow connection number of the hypercube. Isometric subgraphs of hypercubes with the rainbow connection number as small as possible compared to the rainbow connection of the hypercube are constructed....
On the Rainbow Vertex-Connection
A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertexconnected. It was proved that if G is a graph of order n with minimum degree δ, then rvc(G) < 11n/δ. In this paper, we show that rvc(G) ≤ 3n/(δ+1)+5 for [xxx] and n ≥ 290, while rvc(G) ≤ 4n/(δ + 1) + 5...
On the rooted Tutte polynomial
The Tutte polynomial is a generalization of the chromatic polynomial of graph colorings. Here we present an extension called the rooted Tutte polynomial, which is defined on a graph where one or more vertices are colored with prescribed colors. We establish a number of results pertaining to the rooted Tutte polynomial, including a duality relation in the case that all roots reside around a single face of a planar graph.
On the second Laplacian spectral moment of a graph
Kragujevac (M. L. Kragujevac: On the Laplacian energy of a graph, Czech. Math. J. 56(131) (2006), 1207–1213) gave the definition of Laplacian energy of a graph and proved ; equality holds if and only if . In this paper we consider the relation between the Laplacian energy and the chromatic number of a graph and give an upper bound for the Laplacian energy on a connected graph.
On the size of minimal unsatisfiable formulas.