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 79 Next

Displaying 1561 – 1580 of 8549

Showing per page

Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC

Amitayu Banerjee, Zalán Gyenis (2021)

Commentationes Mathematicae Universitatis Carolinae

In set theory without the axiom of choice (AC), we observe new relations of the following statements with weak choice principles. ∘ If in a partially ordered set, all chains are finite and all antichains are countable, then the set is countable. ∘ If in a partially ordered set, all chains are finite and all antichains have size ℵ α , then the set has size ℵ α for any regular ℵ α . ∘ Every partially ordered set without a maximal element has two disjoint cofinal sub sets – CS. ∘ Every partially ordered set...

Chromatic polynomials of hypergraphs

Mieczysław Borowiecki, Ewa Łazuka (2000)

Discussiones Mathematicae Graph Theory

In this paper we present some hypergraphs which are chromatically characterized by their chromatic polynomials. It occurs that these hypergraphs are chromatically unique. Moreover we give some equalities for the chromatic polynomials of hypergraphs generalizing known results for graphs and hypergraphs of Read and Dohmen.

Chromatic Polynomials of Mixed Hypercycles

Julian A. Allagan, David Slutzky (2014)

Discussiones Mathematicae Graph Theory

We color the vertices of each of the edges of a C-hypergraph (or cohypergraph) in such a way that at least two vertices receive the same color and in every proper coloring of a B-hypergraph (or bihypergraph), we forbid the cases when the vertices of any of its edges are colored with the same color (monochromatic) or when they are all colored with distinct colors (rainbow). In this paper, we determined explicit formulae for the chromatic polynomials of C-hypercycles and B-hypercycles

Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs

Ewa Kubicka, Grzegorz Kubicki, Kathleen A. McKeon (2015)

Discussiones Mathematicae Graph Theory

Given graphs G and H, a vertex coloring c : V (G) →ℕ is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ (H,G), is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G, ∑(H,G), is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for ∑(H,G), discuss the computational complexity of finding this parameter for different choices of H, and...

Chvátal-Erdos condition and pancyclism

Evelyne Flandrin, Hao Li, Antoni Marczyk, Ingo Schiermeyer, Mariusz Woźniak (2006)

Discussiones Mathematicae Graph Theory

The well-known Chvátal-Erdős theorem states that if the stability number α of a graph G is not greater than its connectivity then G is hamiltonian. In 1974 Erdős showed that if, additionally, the order of the graph is sufficiently large with respect to α, then G is pancyclic. His proof is based on the properties of cycle-complete graph Ramsey numbers. In this paper we show that a similar result can be easily proved by applying only classical Ramsey numbers.

Chvátal-Erdös type theorems

Jill R. Faudree, Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson, Colton Magnant (2010)

Discussiones Mathematicae Graph Theory

The Chvátal-Erdös theorems imply that if G is a graph of order n ≥ 3 with κ(G) ≥ α(G), then G is hamiltonian, and if κ(G) > α(G), then G is hamiltonian-connected. We generalize these results by replacing the connectivity and independence number conditions with a weaker minimum degree and independence number condition in the presence of sufficient connectivity. More specifically, it is noted that if G is a graph of order n and k ≥ 2 is a positive integer such that κ(G) ≥ k, δ(G) > (n+k²-k)/(k+1),...

Chvátal's Condition cannot hold for both a graph and its complement

Alexandr V. Kostochka, Douglas B. West (2006)

Discussiones Mathematicae Graph Theory

Chvátal’s Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that d i > i or d n - i ≥ n - i . We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.

Ciclos de Hamilton en redes de paso conmutativo y de paso fijo.

Miguel Angel Fiol Mora, José Luis Andrés Yebra (1988)

Stochastica

From a natural generalization to Z2 of the concept of congruence, it is possible to define a family of 2-regular digraphs that we call commutative-step networks. Particular examples of such digraphs are the cartesian product of two directed cycles, C1 x Ch, and the fixed-step network (or 2-step circulant digraph) DN,a,b.In this paper the theory of congruences in Z2 is applied to derive three equivalent characterizations of those commutative-step networks that have a Hamiltonian cycle. Some known...

Circuit and cocircuit partitions of binary matroids

Eunice Gogo Mphako (2006)

Czechoslovak Mathematical Journal

We give an example of a class of binary matroids with a cocircuit partition and we give some characteristics of a set of cocircuits of such binary matroids which forms a partition of the ground set.

Circuit bases of strongly connected digraphs

Petra M. Gleiss, Josef Leydold, Peter F. Stadler (2003)

Discussiones Mathematicae Graph Theory

The cycle space of a strongly connected graph has a basis consisting of directed circuits. The concept of relevant circuits is introduced as a generalization of the relevant cycles in undirected graphs. A polynomial time algorithm for the computation of a minimum weight directed circuit basis is outlined.

Currently displaying 1561 – 1580 of 8549