The chromatic difference sequence of the Cartesian product of graphs

The chromatic difference sequence cds(G) of a graph G with chromatic number n is defined by cds(G) = (a(1), a(2),…, a(n)) if the sum of a(1), a(2),…, a(t) is the maximum number of vertices in an induced t-colorable subgraph of G for t = 1, 2,…, n. The Cartesian product of two graphs G and H, denoted by G□H, has the vertex set V(G□H = V(G) x V(H) and its edge set is given by (x₁, y₁)(x₂, y₂) ε E(G□H) if either x₁ = x₂ and y₁ y₂ ε E(H) or y₁ = y₂ and x₁x₂ ε E(G).

We obtained four main results: the cds of the product of bipartite graphs, the cds of the product of graphs with cds being nondrop flat and first-drop flat, the non-increasing theorem for powers of graphs and cds of powers of circulant graphs.     

Optimal graphs for chromatic polynomials

Let F(n,e) be the collection of all simple graphs with n vertices and e edges, and for G∈F(n,e) let P(G;λ) be the chromatic polynomial of G. A graph G∈F(n,e) is said to be optimal if another graph H∈F(n,e) does not exist with P(H;λ)?P(G;λ) for all λ, with strict inequality holding for some λ. In this paper we derive necessary conditions for bipartite graphs to be optimal, and show that, contrarily to the case of lower bounds, one can find values of n and e for which optimal graphs are not unique. We also derive necessary conditions for bipartite graphs to have the greatest number of cycles of length 4.     

On incompactness for chromatic number of graphs

We deal with incompactness. Assume the existence of non-reflecting stationary set of cofinality κ. We prove that one can define a graph G whose chromatic number is >κ, while the chromatic number of every subgraph G′?G, |G′|<|G| is ≦κ. The main case is κ=?₀.     

Inequalities for the chromatic numbers of graphs

Inequalities for the chromatic numbers of graphs are proved, some of which generalize results of Nordhaus and Gaddum [9] and Dirac [4].     

The chromatic connectivity of graphs

A graphG ischromatically k-connected if every vertex cutset induces a subgraph with chromatic number at leastk. This concept arose in some work, involving the third author, on Ramsey Theory. (For the reference, see the text.) Here we begin the study of chromatic connectivity for its own sake. We show thatG is chromaticallyk-connected iff every homomorphic image of it isk-connected. IfG has no triangles then it is at most chromatically 1-connected, but we prove that the Kneser graphs provide examples ofK ₄-free graphs with arbitrarily large chromatic connectivity. We also verify thatK ₄-free planar graphs are at most chromatically 2-connected.This work was supported by grants from NSERC of Canada.     

Star chromatic numbers of graphs

We investigate the relation between the star-chromatic number (G) and the chromatic number (G) of a graphG. First we give a sufficient condition for graphs under which their starchromatic numbers are equal to their ordinary chromatic numbers. As a corollary we show that for any two positive integersk, g, there exists ak-chromatic graph of girth at leastg whose star-chromatic number is alsok. The special case of this corollary withg=4 answers a question of Abbott and Zhou. We also present an infinite family of triangle-free planar graphs whose star-chromatic number equals their chromatic number. We then study the star-chromatic number of An infinite family of graphs is constructed to show that for each >0 and eachm2 there is anm-connected (m+1)-critical graph with star chromatic number at mostm+. This answers another question asked by Abbott and Zhou.     

Relaxed chromatic numbers of graphs

Given any family of graphsP, theP chromatic number _p (G) of a graphG is the smallest number of classes into whichV(G) can be partitioned such that each class induces a subgraph inP. We study this for hereditary familiesP of two broad types: the graphs containing no subgraph of a fixed graphH, and the graphs that are disjoint unions of subgraphs ofH. We generalize results on ordinary chromatic number and we computeP chromatic number for special choices ofP on special classes of graphs.Research supported in part by ONR Grant N00014-85K0570 and by a grant from the University of Illinois Research Board.     

Path chromatic numbers of graphs

Let the finite, simple, undirected graph G = (V(G), E(G)) be vertex-colored. Denote the distinct colors by 1,2,…,c. Let V_i be the set of all vertices colored j and let <V_i be the subgraph of G induced by V_i. The k-path chromatic number of G, denoted by χ(G; P_k), is the least number c of distinct colors with which V(G) can be colored such that each connected component of V_i is a path of order at most k, 1 ? i ? c. We obtain upper bounds for χ(G; P_k) and χ(G; P_∞) for regular, planar, and outerplanar graphs.     

Inequalities for the Grundy chromatic number of graphs

The Grundy (or First-Fit) chromatic number of a graph G is the maximum number of colors used by the First-Fit coloring of the graph G. In this paper we give upper bounds for the Grundy number of graphs in terms of vertex degrees, girth, clique partition number and for the line graphs. Next we show that if the Grundy number of a graph is large enough then the graph contains a subgraph of prescribed large girth and Grundy number.     

New bounds for the chromatic number of graphs

In this article we first give an upper bound for the chromatic number of a graph in terms of its degrees. This bound generalizes and modifies the bound given in 11 . Next, we obtain an upper bound of the order of magnitude for the coloring number of a graph with small K_2,t (as subgraph), where n is the order of the graph. Finally, we give some bounds for chromatic number in terms of girth and book size. These bounds improve the best known bound, in terms of order and girth, for the chromatic number of a graph when its girth is an even integer. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:110–122, 2008     

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.     

Finite subgraphs of uncountably chromatic graphs

It is consistent that for every function f:ω → ω there is a graph with size and chromatic number ?₁ in which every n‐chromatic subgraph contains at least f(n) vertices (n ≥ 3). This solves a $ 250 problem of Erd?s. It is consistent that there is a graph X with Chr(X)=|X|=?₁ such that if Y is a graph all whose finite subgraphs occur in X then Chr(Y)≤?₂ (so the Taylor conjecture may fail). It is also consistent that if X is a graph with chromatic number at least ?₂ then for every cardinal λ there exists a graph Y with Chr(Y)≥λ all whose finite subgraphs are induced subgraphs of X. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 28–38, 2005     

Fractional chromatic number and circular chromatic number for distance graphs with large clique size

An Erratum has been published for this article in Journal of Graph Theory 48: 329–330, 2005 . Let M be a set of positive integers. The distance graph generated by M, denoted by G(Z, M), has the set Z of all integers as the vertex set, and edges ij whenever |i?j| ∈ M. We investigate the fractional chromatic number and the circular chromatic number for distance graphs, and discuss their close connections with some number theory problems. In particular, we determine the fractional chromatic number and the circular chromatic number for all distance graphs G(Z, M) with clique size at least |M|, except for one case of such graphs. For the exceptional case, a lower bound for the fractional chromatic number and an upper bound for the circular chromatic number are presented; these bounds are sharp enough to determine the chromatic number for such graphs. Our results confirm a conjecture of Rabinowitz and Proulx 22 on the density of integral sets with missing differences, and generalize some known results on the circular chromatic number of distance graphs and the parameter involved in the Wills' conjecture 26 (also known as the “lonely runner conjecture” 1 ). © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 129–146, 2004