-colorings and -bipartite graphs.
Parallel algorithms on interval graphs
Parameters of bar -visibility graphs.
Parity vertex colorings of binomial trees
We show for every k ≥ 1 that the binomial tree of order 3k has a vertex-coloring with 2k+1 colors such that every path contains some color odd number of times. This disproves a conjecture from [1] asserting that for every tree T the minimal number of colors in a such coloring of T is at least the vertex ranking number of T minus one.
Parity vertex colouring of graphs
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),...
Partial covers of graphs
Given graphs G and H, a mapping f:V(G) → V(H) is a homomorphism if (f(u),f(v)) is an edge of H for every edge (u,v) of G. In this paper, we initiate the study of computational complexity of locally injective homomorphisms called partial covers of graphs. We motivate the study of partial covers by showing a correspondence to generalized (2,1)-colorings of graphs, the notion stemming from a practical problem of assigning frequencies to transmitters without interference. We compare the problems of...
Partially complemented representations of digraphs.
Paths through fixed vertices in edge-colored graphs
We study the problem of finding an alternating path having given endpoints and passing through a given set of vertices in edge-colored graphs (a path is alternating if any two consecutive edges are in different colors). In particular, we show that this problem in NP-complete for 2-edge-colored graphs. Then we give a polynomial characterization when we restrict ourselves to 2-edge-colored complete graphs. We also investigate on (s,t)-paths through fixed vertices, i.e. paths of length s+t such that...
Pebbling dynamic graphs in minimal space
Performance considerations on a random graph model for parallel processing
Permanents, Pfaffian orientations, and even directed circuits.
Permutation of sparse matrices to a specific lower BFT using graph decompositions.
Planar embeddability of the vertices of a graph using a fixed point set is NP-hard.
Planar graphs as minimal resolutions of trivariate monomial ideals.
Planar graphs with topological constraints.
Planar ordered sets of width two
Planarity testing and optimal edge insertion with embedding constraints.
p-Median problems in a fuzzy environment.
In this paper a formulation for the fuzzy p-median model in a fuzzy environment is presented. The model allows to find optimal locations of p facilities and their related cost when data related to the node demands and the edge distances are imprecise and uncertain and also to know the degree of certainty of the solution. For the sake of illustration, the proposed model is applied in a reduced map of Kinshasa (Democratic Republic of Congo) obtaining results which are rather than realistic ones.
Polar coordinate drawing of planar graphs with good angular resolution.
Porous media equation on locally finite graphs
In this paper, we consider two typical problems on a locally finite connected graph. The first one is to study the Bochner formula for the Laplacian operator on a locally finite connected graph. The other one is to obtain global nontrivial nonnegative solution to porous-media equation via the use of Aronson-Benilan argument. We use the curvature dimension condition to give a characterization two point graph. We also give a porous-media equation criterion about stochastic completeness of the graph....