All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 4 Next

Displaying 61 – 80 of 134

Showing per page

On multiset colorings of graphs

Futaba Okamoto, Ebrahim Salehi, Ping Zhang (2010)

Discussiones Mathematicae Graph Theory

A vertex coloring of a graph G is a multiset coloring if the multisets of colors of the neighbors of every two adjacent vertices are different. The minimum k for which G has a multiset k-coloring is the multiset chromatic number χₘ(G) of G. For every graph G, χₘ(G) is bounded above by its chromatic number χ(G). The multiset chromatic numbers of regular graphs are investigated. It is shown that for every pair k, r of integers with 2 ≤ k ≤ r - 1, there exists an r-regular graph with multiset chromatic...

On (p, 1)-total labelling of 1-planar graphs

Xin Zhang, Yong Yu, Guizhen Liu (2011)

Open Mathematics

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that the (p, 1)-total labelling number of every 1-planar graph G is at most Δ(G) + 2p − 2 provided that Δ(G) ≥ 8p+4 or Δ(G) ≥ 6p+2 and g(G) ≥ 4. As a consequence, the well-known (p, 1)-total labelling conjecture has been confirmed for some 1-planar graphs.

On partitions of hereditary properties of graphs

Mieczysław Borowiecki, Anna Fiedorowicz (2006)

Discussiones Mathematicae Graph Theory

In this paper a concept 𝓠-Ramsey Class of graphs is introduced, where 𝓠 is a class of bipartite graphs. It is a generalization of well-known concept of Ramsey Class of graphs. Some 𝓠-Ramsey Classes of graphs are presented (Theorem 1 and 2). We proved that 𝓣₂, the class of all outerplanar graphs, is not 𝓓₁-Ramsey Class (Theorem 3). This results leads us to the concept of acyclic reducible bounds for a hereditary property 𝓟 . For 𝓣₂ we found two bounds (Theorem 4). An improvement, in some sense,...

On rainbow connection.

Caro, Yair, Lev, Arie, Roditty, Yehuda, Tuza, Zsolt, Yuster, Raphael (2008)

The Electronic Journal of Combinatorics [electronic only]

On rainbowness of semiregular polyhedra

Stanislav Jendroľ, Štefan Schrötter (2008)

Czechoslovak Mathematical Journal

We introduce the rainbowness of a polyhedron as the minimum number k such that any colouring of vertices of the polyhedron using at least k colours involves a face all vertices of which have different colours. We determine the rainbowness of Platonic solids, prisms, antiprisms and ten Archimedean solids. For the remaining three Archimedean solids this parameter is estimated.

On splitting infinite-fold covers

Márton Elekes, Tamás Mátrai, Lajos Soukup (2011)

Fundamenta Mathematicae

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...

On stratification and domination in graphs

Ralucca Gera, Ping Zhang (2006)

Discussiones Mathematicae Graph Theory

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 γ F ( G ) is the minimum number of red vertices in an F-coloring of G. In...

Currently displaying 61 – 80 of 134