A note on upper bound for chromatic number of a graph.
A note on upper embeddable graphs
A Note On Vertex Colorings Of Plane Graphs
Given an integer valued weighting of all elements of a 2-connected plane graph G with vertex set V , let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) ≠ c(v) for any two adjacent vertices u and v of G. We show that for every 2-connected plane graph there is such a proper vertex coloring with weights in {1, 2, 3}. In a special case, the value 3 is improved to 2.
A note to independent sets in scheduling
The paper studies the bus-journey graphs in the case when they are piecewise expanding and contracting (if described by fathers-sons relations starting with the greatest independent set of nodes). This approach can make it possible to solve the minimization problem of the total service time of crews.
A numerical invariant for finitely generated groups via actions on graphs.
A paintability version of the combinatorial Nullstellensatz, and list colorings of -partite -uniform hypergraphs.
A parametric analysis of the largest induced tree problem in random graphs
A parametrization of the abstract Ramsey theorem.
A partition of connected graphs.
A partition of the Catalan numbers and enumeration of genealogical trees
A special relational structure, called genealogical tree, is introduced; its social interpretation and geometrical realizations are discussed. The numbers of all abstract genealogical trees with exactly n+1 nodes and k leaves is found by means of enumeration of code words. For each n, the form a partition of the n-th Catalan numer Cₙ, that means .
A path(ological) partition problem
Let τ(G) denote the number of vertices in a longest path of the graph G and let k₁ and k₂ be positive integers such that τ(G) = k₁ + k₂. The question at hand is whether the vertex set V(G) can be partitioned into two subsets V₁ and V₂ such that τ(G[V₁] ) ≤ k₁ and τ(G[V₂] ) ≤ k₂. We show that several classes of graphs have this partition property.
A polyhedral study of a two level facility location model
We study an uncapacitated facility location model where customers are served by facilities of level one, then each level one facility that is opened must be assigned to an opened facility of level two. We identify a polynomially solvable case, and study some valid inequalities and facets of the associated polytope.
A polynomial algorithm for minDSC on a subclass of series Parallel graphs
The aim of this paper is to show a polynomial algorithm for the problem minimum directed sumcut for a class of series parallel digraphs. The method uses the recursive structure of parallel compositions in order to define a dominating set of orders. Then, the optimal order is easily reached by minimizing the directed sumcut. It is also shown that this approach cannot be applied in two more general classes of series parallel digraphs.
A Poster about the Old History of Fractional Calculus
MSC 2010: 26A33, 05C72, 33E12, 34A08, 34K37, 35R11, 60G22The fractional calculus (FC) is an area of intensive research and development. In a previous paper and poster we tried to exhibit its recent state, surveying the period of 1966-2010. The poster accompanying the present note illustrates the major contributions during the period 1695-1970, the "old history" of FC.
A prime factor theorem for a generalized direct product
We introduce the concept of neighborhood systems as a generalization of directed, reflexive graphs and show that the prime factorization of neighborhood systems with respect to the the direct product is unique under the condition that they satisfy an appropriate notion of thinness.
A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree.
A problem concerning -pancyclic graphs
A problem on matrices
A proof of menger's theorem by contraction
A short proof of the classical theorem of Menger concerning the number of disjoint AB-paths of a finite graph for two subsets A and B of its vertex set is given. The main idea of the proof is to contract an edge of the graph.
A proof of some Schützenberger-type results for Eulerian paths and circuits on digraphs.