Hall ratio of the Mycielski graphs

Let n(G) denote the number of vertices of a graph G and let α(G) be the independence number of G, the maximum number of pairwise nonadjacent vertices of G. The Hall ratio of a graph G is defined by

     

List colorings with measurable sets

The measurable list chromatic number of a graph G is the smallest number ξ such that if each vertex v of G is assigned a set L(v) of measure ξ in a fixed atomless measure space, then there exist sets such that each c(v) has measure one and for every pair of adjacent vertices v and v'. We provide a simpler proof of a measurable generalization of Hall's theorem due to Hilton and Johnson [J Graph Theory 54 (2007), 179–193] and show that the measurable list chromatic number of a finite graph G is equal to its fractional chromatic number. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 229–238, 2008     

List multicoloring problems involving the k‐fold Hall numbers

We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ?5k/3?; furthermore, the same is not true with shorter list lengths. In terms of h^(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h^(k)(C₄)=2k??k/3?. For longer cycles it is known that h^(k)(C_n)=2k, for n odd, and 2k??k/(n?1)?≤h^(k)(C_n)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C₄). We prove that if G is the diamond (a four‐cycle with a diagonal), then h^(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h^(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.     

List multicolorings of graphs with measurable sets

In an ordinary list multicoloring of a graph, the vertices are “colored” with subsets of pre‐assigned finite sets (called “lists”) in such a way that adjacent vertices are colored with disjoint sets. Here we consider the analog of such colorings in which the lists are measurable sets from an arbitrary atomless, semifinite measure space, and the color sets are to have prescribed measures rather than prescribed cardinalities. We adapt a proof technique of Bollobás and Varopoulos to prove an analog of one of the major theorems about ordinary list multicolorings, a generalization and extension of Hall's marriage theorem, due to Cropper, Gyárfás, and Lehel. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 179–193, 2007     

A note on acyclic edge coloring of complete bipartite graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a^′(G). Let Δ=Δ(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K_n,n. Alon, McDiarmid and Reed observed that a^′(K_p−1,p−1)=p for every prime p. In this paper we prove that a^′(K_p,p)≤p+2=Δ+2 when p is prime. Basavaraju, Chandran and Kummini proved that a^′(K_n,n)≥n+2=Δ+2 when n is odd, which combined with our result implies that a^′(K_p,p)=p+2=Δ+2 when p is an odd prime. Moreover we show that if we remove any edge from K_p,p, the resulting graph is acyclically Δ+1=p+1-edge-colorable.     

Complete graphs and complete bipartite graphs without rainbow path

Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs $G$ and $H$, the $k$-colored Gallai–Ramsey number $g{r}_k(G:H)$ is defined to be the minimum integer $n$ such that $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ge k$ and for every $N\ge n$, every rainbow $G$-free coloring (using all $k$ colors) of the complete graph $K_N$ contains a monochromatic copy of $H$. In this paper, we first provide some exact values and bounds of $g{r}_k(P_5:K_t)$. Moreover, we define the $k$-colored bipartite Gallai–Ramsey number $bg{r}_k(G:H)$ as the minimum integer $n$ such that $n^2\ge k$ and for every $N\ge n$, every rainbow $G$-free coloring (using all $k$ colors) of the complete bipartite graph $K_{N,N}$ contains a monochromatic copy of $H$. Furthermore, we describe the structures of complete bipartite graph $K_{n,n}$ with no rainbow $P_4$ and $P_5$, respectively. Finally, we find the exact values of $bg{r}_k(P_4:K_{s,t})$ ($1\le s\le t$), $bg{r}_k(P_4:F)$ (where $F$ is a subgraph of $K_{s,t}$), $bg{r}_k(P_5:K_{1,t})$ and $bg{r}_k(P_5:K_{2,t})$ by using the structural results.     

Fractional chromatic numbers of cones over graphs

We introduce a construction called the cone over a graph. It is a natural generalisation of Mycielski's construction. We give a formula for the fractional chromatic numbers of all cones over graphs, which generalizes that given in 3 for Mycielski's construction. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 87–94, 2001     

A topological lower bound for the circular chromatic number of Schrijver graphs

In this paper, we prove that the Kneser graphs defined on a ground set of n elements, where n is even, have their circular chromatic numbers equal to their chromatic numbers. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 257–261, 2005     

Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs

For a given graph F we consider the family of (finite) graphs G with the Ramsey property for F, that is the set of such graphs G with the property that every two‐coloring of the edges of G yields a monochromatic copy of F. For F being a triangle Friedgut, Rödl, Ruciński, and Tetali (2004) established the sharp threshold for the Ramsey property in random graphs. We present a simpler proof of this result which extends to a more general class of graphs F including all cycles. The proof is based on Friedgut's criteria (1999) for sharp thresholds and on the recently developed container method for independent sets in hypergraphs by Saxton and Thomason and by Balogh, Morris and Samotij. The proof builds on some recent work of Friedgut et al. who established a similar result for van der Waerden's theorem.     

On chromatic‐choosable graphs

A graph is chromatic‐choosable if its choice number coincides with its chromatic number. It is shown in this article that, for any graph G, if we join a sufficiently large complete graph to G, then we obtain a chromatic‐choosable graph. As a consequence, if the chromatic number of a graph G is close enough to the number of vertices in G, then G is chromatic‐choosable. We also propose a conjecture related to this fact. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 130–135, 2002     

On the complete chromatic number of Halin graphs

ThisresearchissupportedbytheNationalNaturalScienceFoundationofChina.Write.1.IntroductionDefinition1.FOrany3-connectedplanargraphG(V,E,F)withA(G)23,iftheboundaryedgesoffacefowhichisadjacenttotheothersareremoved,itbecomesatree,andthedegreeofeachvertexofV(fo)is3,andthenGiscalledaHalingraph;foiscalledtheouterfaceofG,andtheotherscalledtheinteriorfaces,thevenicesonthefacefoarecalledtheoutervenices,theoillersarecalledtheinterior...ti..,tll.ForanyplanargraphG(V,E,F),f,f'eF,fisadjacenttof'ifan…     

Characterization of graphs with hall number 2

Hall's condition is a simple requirement that a graph G and list assignment L must satisfy if G is to have a proper L‐colouring. The Hall number of G is the smallest integer m such that whenever the lists on the vertices each has size at least m and Hall's condition is satisfied a proper L‐colouring exists. Hilton and P.D. Johnson introduced the parameter and showed that a graph has Hall number 1 if and only if every block is a clique. In this paper we give a forbidden‐induced‐subgraph characterization of graphs with Hall number 2. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 81–100, 2004     

Game chromatic number of strong product graphs

The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths.     

On covering graphs by complete bipartite subgraphs

We prove that, if a graph with e edges contains m vertex-disjoint edges, then m²/e complete bipartite subgraphs are necessary to cover all its edges. Similar lower bounds are also proved for fractional covers. For sparse graphs, this improves the well-known fooling set lower bound in communication complexity. We also formulate several open problems about covering problems for graphs whose solution would have important consequences in the complexity theory of boolean functions.     

The fractional chromatic number, the Hall ratio, and the lexicographic product

Let χ_f denote the fractional chromatic number and ρ the Hall ratio, and let the lexicographic product of G and H be denoted GlexH. Main results: (i) ρ(GlexH)≤χ_f(G)ρ(H); (ii) if ρ(G)=χ_f(G) then ρ(GlexH)=ρ(G)ρ(H) for all H; (iii) χ_f−ρ is unbounded. In addition, the question of how big χ_f/ρ can be is discussed.     

Hall's theorem for hypergraphs

We prove a hypergraph version of Hall's theorem. The proof is topological. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 83–88, 2000     

Hall number for list colorings of graphs: Extremal results

Given a graph G=(V,E) and sets L(v) of allowed colors for each v∈V, a list coloring of G is an assignment of colors φ(v) to the vertices, such that φ(v)∈L(v) for all v∈V and φ(u)≠φ(v) for all uv∈E. The choice number of G is the smallest natural number k admitting a list coloring for G whenever |L(v)|≥k holds for every vertex v. This concept has an interesting variant, called Hall number, where an obvious necessary condition for colorability is put as a restriction on the lists L(v). (On complete graphs, this condition is equivalent to the well-known one in Hall’s Marriage Theorem.) We prove that vertex deletion or edge insertion in a graph of order n>3 may make the Hall number decrease by as much as n−3. This estimate is tight for all n. Tightness is deduced from the upper bound that every graph of order n has Hall number at most n−2. We also characterize the cases of equality; for n≥6 these are precisely the graphs whose complements are K₂∪(n−2)K₁, P₄∪(n−4)K₁, and C₅∪(n−5)K₁. Our results completely solve a problem raised by Hilton, Johnson and Wantland [A.J.W. Hilton, P.D. Johnson, Jr., E. B. Wantland, The Hall number of a simple graph, Congr. Numer. 121 (1996), 161-182, Problem 7] in terms of the number of vertices, and strongly improve some estimates due to Hilton and Johnson [A.J.W. Hilton, P.D. Johnson, Jr., The Hall number, the Hall index, and the total Hall number of a graph, Discrete Appl. Math. 94 (1999), 227-245] as a function of maximum degree.