Chromatic number of products of graphs
Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC
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 numbers of the strong product of odd cycles
Chromatic polynomials of hypergraphs
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
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 roots of a ring of four cliques.
Chromatic statistics for triangulations and Fuß-Catalan complexes.
Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs
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...
Chromatic sums revisited.
Chromatically unique bipartite graphs with certain 3-independent partition numbers. II.
Chromatically unique multibridge graphs.
Chung-Feller property in view of generating functions.
Chvátal-Erdos condition and pancyclism
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
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
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 or . 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.
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...
Circle-packing connections with random walks and a finite volume method
Circuit and cocircuit partitions of binary matroids
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
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.
Circuits et arbres de circulation d'un graphe fortement connexe