Circumference, chromatic number and online coloring

Erd?s conjectured that if G is a triangle free graph of chromatic number at least k≥3, then it contains an odd cycle of length at least k ^2?o(1) [13,15]. Nothing better than a linear bound ([3], Problem 5.1.55 in [16]) was so far known. We make progress on this conjecture by showing that G contains an odd cycle of length at least Ω(k log logk). Erd?s’ conjecture is known to hold for graphs with girth at least five. We show that if a graph with girth four is C ₅ free, then Erd?s’ conjecture holds. When the number of vertices is not too large we can prove better bounds on χ. We also give bounds on the chromatic number of graphs with at most r cycles of length 1 mod k, or at most s cycles of length 2 mod k, or no cycles of length 3 mod k. Our techniques essentially consist of using a depth first search tree to decompose the graph into ordered paths, which are then fed to an online coloring algorithm. Using this technique we give simple proofs of some old results, and also obtain several other results. We also obtain a lower bound on the number of colors which an online coloring algorithm needs to use to color triangle free graphs.     

On the concentration of the chromatic number of a random hypergraph

The problem on the limit distribution of the chromatic number of a random uniform hypergraph in the sparse case is studied. It is shown that, for most parameters values, the limit distribution of the chromatic number is concentrated at precisely one point, which can be found explicitly.     

Critical hypergraphs for the weak chromatic number

Instead of removing a vertex or an edge from a hypergraph H, one may add to some edges of H new vertices (not necessarily belonging to V_H). The weak chromatic number of H tends to drop by this operation. This suggests the definition of an order relation ≥ on the set $\text{S}$ of all Sperner hypergraphs on a universal set V of vertices. The corresponding criticality study leads to unifying and interesting results: reconstruction of critical hypergraphs and two general characterizations of k-chromatic critical hypergraphs (k ≥ 3), from which a special characterization of 3-chromatic critical hypergraphs can be derived.     

On coloring graphs with locally small chromatic number

In 1973, P. Erdös conjectured that for eachkε2, there exists a constantc _k so that ifG is a graph onn vertices andG has no odd cycle with length less thanc _k n ^1/k , then the chromatic number ofG is at mostk+1. Constructions due to Lovász and Schriver show thatc _k , if it exists, must be at least 1. In this paper we settle Erdös’ conjecture in the affirmative. We actually prove a stronger result which provides an upper bound on the chromatic number of a graph in which we have a bound on the chromatic number of subgraphs with small diameter.     

Acyclic graph coloring and the complexity of the star chromatic number

Star chromatic number, introduced by A. Vince, is a natural generalization of chromatic number. We consider the question, “When is χ* < χ?” We show that χ* < χ if and only if a particular digraph is acyclic and that the decisioin problem associated with this question is probably not in NP though it is both NP-hard and NP-easy. © 1993 John Wiley & Sons, Inc.     

On cycle systems with specified weak chromatic number

A weak k-colouring of an m-cycle system is a colouring of the vertices of the system with k colours in such a way that no cycle of the system has all of its vertices receive the same colour. An m-cycle system is said to be weakly k-chromatic if it has a weak k-colouring but no weak (k−1)-colouring. In this paper we show that for all k?2 and m?3 with (k,m)≠(2,3) there is a weakly k-chromatic m-cycle system of order v for all sufficiently large admissible v.     

Random lifts of graphs: Independence and chromatic number

For a graph G, a random n‐lift of G has the vertex set V(G)×[n] and for each edge [u, v] ∈ E(G), there is a random matching between {u}×[n] and {v}×[n]. We present bounds on the chromatic number and on the independence number of typical random lifts, with G fixed and n→∞. For the independence number, upper and lower bounds are obtained as solutions to certain optimization problems on the base graph. For a base graph G with chromatic number χ and fractional chromatic number χ_f, we show that the chromatic number of typical lifts is bounded from below by const ? and also by const ? χ_f/log²χ_f (trivially, it is bounded by χ from above). We have examples of graphs where the chromatic number of the lift equals χ almost surely, and others where it is a.s. O(χ/logχ). Many interesting problems remain open. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 1–22, 2002     

An extremal problem in hypergraph coloring

F(n, r, k) is defined to be the minimum number of edges in an r graph on n vertices in which there exists a strongly colored edge in every equipartite k-coloring. Approximate values are given for this function in the general case, and the problem is solved in the particular case of graphs.     

On incidentor coloring in a hypergraph

The problem is considered of the incidentor p-coloring of directed and undirected hypergraphs. The exact lower and upper bounds are given of the minimum necessary number of colors.     

Applications of hypergraph coloring to coloring graphs not inducing certain trees

We present a simple result on coloring hypergraphs and use it to obtain bounds on the chromatic number of graphs which do not induce certain trees.     

The coloring complex and cyclic coloring complex of a complete k-uniform hypergraph

In this paper, we study the homology of the coloring complex and the cyclic coloring complex of a complete k-uniform hypergraph. We show that the coloring complex of a complete k-uniform hypergraph is shellable, and we determine the rank of its unique nontrivial homology group in terms of its chromatic polynomial. We also show that the dimension of the $(n?k?1)\text{st}$ homology group of the cyclic coloring complex of a complete k-uniform hypergraph is given by a binomial coefficient. Further, we discuss a complex whose r-faces consist of all ordered set partitions $[B_1,\dots ,B_{r+2}]$ where none of the $B_i$ contain a hyperedge of the complete k-uniform hypergraph H and where $1\in B_1$. It is shown that the dimensions of the homology groups of this complex are given by binomial coefficients. As a consequence, this result gives the dimensions of the multilinear parts of the cyclic homology groups of $\mathbb{C}[x_1,\dots ,x_n]/\{x_{i_1}\dots x_{i_k}|i_1\dots i_k\text{is a hyperedge of}H\}$.     

Post's closed systems and the weak chromatic number of hypergraphs

In the Post lattice of the families of closed systems (i.e. sets of boolean functions closed with respect to composition) the particular systems of monotonic functions are closely related to the classification of hypergraphs by their weak chromatic numbers. It is shown also that for k>3, the k-chromatic hypergraphs can be built from the complete graph K.     

Packing chromatic number versus chromatic and clique number

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets \(V_i\), \(i\in [k]\), where each \(V_i\) is an i-packing. In this paper, we investigate for a given triple (a, b, c) of positive integers whether there exists a graph G such that \(\omega (G) = a\), \(\chi (G) = b\), and \(\chi _{\rho }(G) = c\). If so, we say that (a, b, c) is realizable. It is proved that \(b=c\ge 3\) implies \(a=b\), and that triples \((2,k,k+1)\) and \((2,k,k+2)\) are not realizable as soon as \(k\ge 4\). Some of the obtained results are deduced from the bounds proved on the packing chromatic number of the Mycielskian. Moreover, a formula for the independence number of the Mycielskian is given. A lower bound on \(\chi _{\rho }(G)\) in terms of \(\Delta (G)\) and \(\alpha (G)\) is also proved.     

Random regular graphs of non-constant degree: Concentration of the chromatic number

In this work we show that with high probability the chromatic number of a graph sampled from the random regular graph model G_n,d for d=o(n^1/5) is concentrated in two consecutive values, thus extending a previous result of Achlioptas and Moore. This concentration phenomena is very similar to that of the binomial random graph model G(n,p) with . Our proof is largely based on ideas of Alon and Krivelevich who proved this two-point concentration result for G(n,p) for p=n^−δ where δ>1/2. The main tool used to derive such a result is a careful analysis of the distribution of edges in G_n,d, relying both on the switching technique and on bounding the probability of exponentially small events in the configuration model.     

The Hodge structure of the coloring complex of a hypergraph

Let G be a simple graph with n vertices. The coloring complex Δ(G) was defined by Steingrímsson, and the homology of Δ(G) was shown to be nonzero only in dimension n−3 by Jonsson. Hanlon recently showed that the Eulerian idempotents provide a decomposition of the homology group H_n−3(Δ(G)) where the dimension of the jth component in the decomposition, , equals the absolute value of the coefficient of λ^j in the chromatic polynomial of G, χ_G(λ).Let H be a hypergraph with n vertices. In this paper, we define the coloring complex of a hypergraph, Δ(H), and show that the coefficient of λ^j in χ_H(λ) gives the Euler Characteristic of the jth Hodge subcomplex of the Hodge decomposition of Δ(H). We also examine conditions on a hypergraph, H, for which its Hodge subcomplexes are Cohen–Macaulay, and thus where the absolute value of the coefficient of λ^j in χ_H(λ) equals the dimension of the jth Hodge piece of the Hodge decomposition of Δ(H). We also note that the Euler Characteristic of the jth Hodge subcomplex of the Hodge decomposition of the intersection of coloring complexes is given by the coefficient of jth term in the associated chromatic polynomial.     

An uncertain chromatic number of an uncertain graph based on $$\alpha $$-cut coloring

An uncertain graph is a graph in which the edges are indeterminate and the existence of edges are characterized by belief degrees which are uncertain measures. This paper aims to bring graph coloring and uncertainty theory together. A new approach for uncertain graph coloring based on an \(\alpha \)-cut of an uncertain graph is introduced in this paper. Firstly, the concept of \(\alpha \)-cut of uncertain graph is given and some of its properties are explored. By means of \(\alpha \)-cut coloring, we get an \(\alpha \)-cut chromatic number and examine some of its properties as well. Then, a fact that every \(\alpha \)-cut chromatic number may be a chromatic number of an uncertain graph is obtained, and the concept of uncertain chromatic set is introduced. In addition, an uncertain chromatic algorithm is constructed. Finally, a real-life decision making problem is given to illustrate the application of the uncertain chromatic set and the effectiveness of the uncertain chromatic algorithm.     

On the cyclomatic number of a hypergraph

This note generalizes the notion of cyclomatic number (or cycle rank) from Graph Theory to Hypergraph Theory and links it up with the concept of planarity in hypergraphs which was recently introduced by R.P. Jones. Sharp bounds are obtained for the cyclomatic number of the planar hypergraphs and, further, it is shown that the upper bound is attainable if, and only if the hypergraph satisfies Krewera's condition.