Hall parameters of complete and complete bipartite graphs

Given a graph G, for each υ ∈V(G) let L(υ) be a list assignment to G. The well‐known choice number c(G) is the least integer j such that if |L(υ)| ≥j for all υ ∈V(G), then G has a proper vertex colouring ? with ?(υ) ∈ L (υ) (?υ ∈V(G)). The Hall number h(G) is like the choice number, except that an extra non‐triviality condition, called Hall's condition, has to be satisfied by the list assignment. The edge‐analogue of the Hall number is called the Hall index, h′(G), and the total analogue is called the total Hall number, h″(G), of G. If the stock of colours from which L(υ) is selected is restricted to a set of size k, then the analogous numbers are called k‐restricted, or restricted, Hall parameters, and are denoted by h_k(G), h′_k(G) and h″_k(G). Our main object in this article is to determine, or closely bound, h′(K), h″(K_n), h′(K_m,n) and h′_k(K_m,n). We also answer some hitherto unresolved questions about Hall parameters. We show in particular that there are examples of graphs G with h′(G)?h′(G ? e)>1. We show that there are examples of graphs G and induced subgraphs H with h_k(G)<h_k(H) [this phenomenon cannot occur with unrestricted Hall numbers]. We also give an example of a graph G and an integer k such that h_k(G)<χ(G)<h(G). © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 208–237, 2002     

Binding Number,Minimum Degree,and Cycle Structure in Graphs

A well‐known theorem of Woodall states that if a graph G has binding number at least 3/2, then G is hamiltonian. We generalize Woodall's theorem as follows.     

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.     

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     

Graph colourings with forbidden k-coloured subgraphs

Abstract

For a set F of graphs and a natural number k, an (F, k)-colouring of a graph G is a proper colouring of V (G) such that no subgraph of G isomorphic to an element of F is coloured with at most k colours. Equivalently, if P is the class of all graphs that do not contain an element of F as a subgraph, a χP,k colouring of G is a proper colouring such that the union of at most k colour classes induces a graph in P. The smallest number of colours in such a colouring of G, if it exists, is denoted by χP,k (G). We give some general results on χP,k-colourings and investigate values of χP,k (G) for some choices of P and classes of graphs G.     

A Characterization of b‐Perfect Graphs

A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph G is the largest integer k such that G admits a b‐coloring with k colors. A graph is b‐perfect if the b‐chromatic number is equal to the chromatic number for every induced subgraph of G. We prove that a graph is b‐perfect if and only if it does not contain as an induced subgraph a member of a certain list of 22 graphs. This entails the existence of a polynomial‐time recognition algorithm and of a polynomial‐time algorithm for coloring exactly the vertices of every b‐perfect graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:95–122, 2012     

Acyclic edge coloring of graphs with maximum degree 4

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic 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). It was conjectured by Alon, Sudakov, and Zaks that for any simple and finite graph G, a′(G)?Δ + 2, where Δ=Δ(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Δ(G)?4, with the additional restriction that m?2n?1, where n is the number of vertices and m is the number of edges in G. Note that for any graph G, m?2n, when Δ(G)?4. It follows that for any graph G if Δ(G)?4, then a′(G)?7. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 192–209, 2009     

On an anti‐Ramsey problem of Burr,Erdős,Graham, and T. Sós

Given a graph L, in this article we investigate the anti‐Ramsey number χ_S(n,e,L), defined to be the minimum number of colors needed to edge‐color some graph G(n,e) with n vertices and e edges so that in every copy of L in G all edges have different colors. We call such a copy of L totally multicolored (TMC). In 7 among many other interesting results and problems, Burr, Erd?s, Graham, and T. Sós asked the following question: Let L be a connected bipartite graph which is not a star. Is it true then that In this article, we prove a slightly weaker statement, namely we show that the statement is true if L is a connected bipartite graph, which is not a complete bipartite graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 147–156, 2006     

Planar graphs without 4‐cycles are acyclically 6‐choosable

A proper vertex coloring of a graph G=(V, E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L‐list colorable if for a given list assignment L={L(v)|v∈V}, there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L‐list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k‐choosable. In this paper we prove that every planar graph G without 4‐cycles is acyclically 6‐choosable. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 307–323, 2009     

Parity vertex colouring of plane graphs

A proper vertex colouring of a 2-connected plane graph G is a parity vertex colouring if for each face f and each colour c, either no vertex or an odd number of vertices incident with f is coloured with c. The minimum number of colours used in such a colouring of G is denoted by χ_p(G).In this paper, we prove that χ_p(G)≤118 for every 2-connected plane graph G.     

Acyclic 5‐choosability of planar graphs without small cycles

A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L‐list colorable if for a given list assignment L = {L(v): v: ∈ V}, there exists a proper acyclic coloring ? of G such that ?(v) ∈ L(v) for all v ∈ V. If G is acyclically L‐list colorable for any list assignment with |L (v)|≥ k for all v ∈ V, then G is acyclically k‐choosable. In this article, we prove that every planar graph G without 4‐ and 5‐cycles, or without 4‐ and 6‐cycles is acyclically 5‐choosable. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 245–260, 2007     

Acyclic Edge Coloring of Triangle‐Free Planar Graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic 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). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G) ? Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition |E(H)| ? 2|V(H)|?1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a′(G) ? Δ + 3. Triangle‐free planar graphs satisfy Property A. We infer that a′(G) ? Δ + 3, if G is a triangle‐free planar graph. Another class of graph which satisfies Property A is 2‐fold graphs (union of two forests). © 2011 Wiley Periodicals, Inc. J Graph Theory     

Adaptable chromatic number of graph products

A colouring of the vertices of a graph (or hypergraph) G is adapted to a given colouring of the edges of G if no edge has the same colour as both (or all) its vertices. The adaptable chromatic number of G is the smallest integer k such that each edge-colouring of G by colours 1,2,…,k admits an adapted vertex-colouring of G by the same colours 1,2,…,k. (The adaptable chromatic number is just one more than a previously investigated notion of chromatic capacity.) The adaptable chromatic number of a graph G is smaller than or equal to the ordinary chromatic number of G. While the ordinary chromatic number of all (categorical) powers G^k of G remains the same as that of G, the adaptable chromatic number of G^k may increase with k. We conjecture that for all sufficiently large k the adaptable chromatic number of G^k equals the chromatic number of G. When G is complete, we prove this conjecture with k≥4, and offer additional evidence suggesting it may hold with k≥2. We also discuss other products and propose several open problems.     

On minimally b-imperfect graphs

A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbour in all other color classes. The b-chromatic number of a graph G is the largest integer k such that G admits a b-coloring with k colors. A graph is b-perfect if the b-chromatic number is equal to the chromatic number for every induced subgraph H of G. A graph is minimally b-imperfect if it is not b-perfect and every proper induced subgraph is b-perfect. We give a list of minimally b-imperfect graphs, conjecture that a graph is b-perfect if and only if it does not contain a graph from this list as an induced subgraph, and prove this conjecture for diamond-free graphs, and graphs with chromatic number at most three.     

Weak Borel chromatic numbers

Given a graph G whose set of vertices is a Polish space X, the weak Borel chromatic number of G is the least size of a family of pairwise disjoint G ‐independent Borel sets that covers all of X. Here a set of vertices of a graph G is independent if no two vertices in the set are connected by an edge. We show that it is consistent with an arbitrarily large size of the continuum that every closed graph on a Polish space either has a perfect clique or has a weak Borel chromatic number of at most ?₁. We observe that some weak version of Todorcevic's Open Coloring Axiom for closed colorings follows from MA. Slightly weaker results hold for F_σ‐graphs. In particular, it is consistent with an arbitrarily large size of the continuum that every locally countable F_σ‐graph has a Borel chromatic number of at most ?₁. We refute various reasonable generalizations of these results to hypergraphs (© 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A sufficient condition for planar graphs to be acyclically 5‐choosable

A proper vertex coloring of a graph G = (V, E) is acyclic if G contains no bicolored cycle. Given a list assignment L = {L(v)|v∈V} of G, we say G is acyclically L‐list colorable if there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L‐list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k‐choosable. In this article we prove that every planar graph without 4‐cycles and without intersecting triangles is acyclically 5‐choosable. This improves the result in [M. Chen and W. Wang, Discrete Math 308 (2008), 6216–6225], which says that every planar graph without 4‐cycles and without two triangles at distance less than 3 is acyclically 5‐choosable. © 2011 Wiley Periodicals, Inc. J Graph Theory     

On characterizing Vizing's edge colouring bound

We consider multigraphs G for which equality holds in Vizing's classical edge colouring bound χ′(G)≤Δ + µ, where Δ denotes the maximum degree and µ denotes the maximum edge multiplicity of G. We show that if µ is bounded below by a logarithmic function of Δ, then G attains Vizing's bound if and only if there exists an odd subset S?V(G) with |S|≥3, such that |E[S]|>((|S| ? 1)/2)(Δ + µ ? 1). The famous Goldberg–Seymour conjecture states that this should hold for all µ≥2. We also prove a similar result concerning the edge colouring bound χ′(G)≤Δ + ?µ/?g/2??, due to Steffen (here g denotes the girth of the underlying graph). Finally we give a general approximation towards the Goldberg‐Seymour conjecture in terms of Δ and µ. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:160‐168, 2012     

Achromatic number of fragmentable graphs

A complete coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at least one edge. The achromatic number ψ(G) is the greatest number of colors in such a coloring. We say a class of graphs is fragmentable if for any positive ε, there is a constant C such that any graph in the class can be broken into pieces of size at most C by removing a proportion at most ε of the vertices. Examples include planar graphs and grids of fixed dimension. Determining the achromatic number of a graph is NP‐complete in general, even for trees, and the achromatic number is known precisely for only very restricted classes of graphs. We extend these classes very considerably, by giving, for graphs in any class which is fragmentable, triangle‐free, and of bounded degree, a necessary and sufficient condition for a sufficiently large graph to have a complete coloring with a given number of colors. For the same classes, this gives a tight lower bound for the achromatic number of sufficiently large graphs, and shows that the achromatic number can be determined in polynomial time. As examples, we give exact values of the achromatic number for several graph families. © 2009 Wiley Periodicals, Inc. J Graph Theory 65:94–114, 2010     

Proof of a conjecture on game domination

Let G(V, E) be a simple, undirected graph where V is the set of vertices and E is the set of edges. A b‐dimensional cube is a Cartesian product I₁×I₂×···×I_b, where each I_i is a closed interval of unit length on the real line. The cubicity of G, denoted by cub(G), is the minimum positive integer b such that the vertices in G can be mapped to axis parallel b‐dimensional cubes in such a way that two vertices are adjacent in G if and only if their assigned cubes intersect. An interval graph is a graph that can be represented as the intersection of intervals on the real line—i.e. the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. Suppose S(m) denotes a star graph on m+1 nodes. We define claw number ψ(G) of the graph to be the largest positive integer m such that S(m) is an induced subgraph of G. It can be easily shown that the cubicity of any graph is at least ?log₂ψ(G)?. In this article, we show that for an interval graph G ?log₂ψ(G)??cub(G)??log₂ψ(G)?+2. It is not clear whether the upper bound of ?log₂ψ(G)?+2 is tight: till now we are unable to find any interval graph with cub(G)>?log₂ψ(G)?. We also show that for an interval graph G, cub(G)??log₂α?, where α is the independence number of G. Therefore, in the special case of ψ(G)=α, cub(G) is exactly ?log₂α₂?. The concept of cubicity can be generalized by considering boxes instead of cubes. A b‐dimensional box is a Cartesian product I₁×I₂×···×I_b, where each I_i is a closed interval on the real line. The boxicity of a graph, denoted box(G), is the minimum k such that G is the intersection graph of k‐dimensional boxes. It is clear that box(G)?cub(G). From the above result, it follows that for any graph G, cub(G)?box(G)?log₂α?. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 323–333, 2010