List Colorings with Distinct List Sizes,the Case of Complete Bipartite Graphs

Let be a function on the vertex set of the graph . The graph G is f‐choosable if for every collection of lists with list sizes specified by f there is a proper coloring using colors from the lists. The sum choice number, , is the minimum of , over all functions f such that G is f‐choosable. It is known (Alon, Surveys in Combinatorics, 1993 (Keele), London Mathematical Society Lecture Note Series, Vol. 187, Cambridge University Press, Cambridge, 1993, pp. 1–33, Random Struct Algor 16 (2000), 364–368) that if G has average degree d, then the usual choice number is at least , so they grow simultaneously. In this article, we show that can be bounded while the minimum degree . Our main tool is to give tight estimates for the sum choice number of the unbalanced complete bipartite graph .     

Cycle‐Saturated Graphs with Minimum Number of Edges

A graph G is called H‐saturated if it does not contain any copy of H, but for any edge e in the complement of G, the graph contains some H. The minimum size of an n‐vertex H‐saturated graph is denoted by . We prove holds for all , where is a cycle with length k. A graph G is H‐semisaturated if contains more copies of H than G does for . Let be the minimum size of an n‐vertex H‐semisaturated graph. We have We conjecture that our constructions are optimal for . © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 203–215, 2013     

k‐Kings in k‐Quasitransitive Digraphs

Let D be a digraph with vertex set and arc set . A vertex x is a k‐king of D, if for every , there is an ‐path of length at most k. A subset N of is k‐independent if for every pair of vertices , we have and ; it is l‐absorbent if for every there exists such that . A ‐kernel of D is a k‐independent and l‐absorbent subset of . A k‐kernel is a ‐kernel. A digraph D is k‐quasitransitive, if for any path of length k, x₀ and are adjacent. In this article, we will prove that a k‐quasitransitive digraph with has a k‐king if and only if it has a unique initial strong component and the unique initial strong component is not isomorphic to an extended ‐cycle where each has at least two vertices. Using this fact, we show that every strong k‐quasitransitive digraph has a ‐kernel.     

Finding for a Surface Σ of Characteristic −4

For each surface Σ, we define max G is a class two graph of maximum degree that can be embedded in . Hence, Vizing's Planar Graph Conjecture can be restated as if Σ is a sphere. In this article, by applying some newly obtained adjacency lemmas, we show that if Σ is a surface of characteristic . Until now, all known satisfy . This is the first case where .     

The Set of Circular Flow Numbers of Regular Graphs

This article determines the set of the circular flow numbers of regular graphs. Let be the set of the circular flow numbers of graphs, and be the set of the circular flow numbers of d‐regular graphs. If d is even, then . For it is known 6 that . We show that . Hence, the interval is the only gap for circular flow numbers of ‐regular graphs between and 5. Furthermore, if Tutte's 5‐flow conjecture is false, then it follows, that gaps for circular flow numbers of graphs in the interval [5, 6] are due for all graphs not just for regular graphs.     

Minors in ‐ Chromatic Graphs,II

Let denote the graph obtained from the complete graph by deleting the edges of some ‐subgraph. The author proved earlier that for each fixed s and , every graph with chromatic number has a minor. This confirmed a partial case of the corresponding conjecture by Woodall and Seymour. In this paper, we show that the statement holds already for much smaller t, namely, for .     

Improper Coloring of Sparse Graphs with a Given Girth,II: Constructions

A graph G is ‐colorable if can be partitioned into two sets and so that the maximum degree of is at most j and of is at most k. While the problem of verifying whether a graph is (0, 0)‐colorable is easy, the similar problem with in place of (0, 0) is NP‐complete for all nonnegative j and k with . Let denote the supremum of all x such that for some constant every graph G with girth g and for every is ‐colorable. It was proved recently that . In a companion paper, we find the exact value . In this article, we show that increasing g from 5 further on does not increase much. Our constructions show that for every g, . We also find exact values of for all g and all .     

On the Multichromatic Number of s‐Stable Kneser Graphs

For positive integers n and s, a subset [n] is s‐stable if for distinct . The s‐stable r‐uniform Kneser hypergraph is the r‐uniform hypergraph that has the collection of all s‐stable k‐element subsets of [n] as vertex set and whose edges are formed by the r‐tuples of disjoint s‐stable k‐element subsets of [n]. Meunier ( 21 ) conjectured that for positive integers with , and , the chromatic number of s‐stable r ‐uniform Kneser hypergraphs is equal to . It is a generalized version of the conjecture proposed by Alon et al. ( 1 ). Alon et al. ( 1 ) confirmed Meunier's conjecture for with arbitrary positive integer q. Lin et al. ( 17 ) studied the kth chromatic number of the Mycielskian of the ordinary Kneser graphs for . They conjectured that for . The case was proved by Mycielski ( 22 ). Lin et al. ( 17 ) confirmed their conjecture for , or when n is a multiple of k or . In this paper, we investigate the multichromatic number of the usual s ‐stable Kneser graphs . With the help of Fan's (1952) combinatorial lemma, we show that Meunier's conjecture is true for r is a power of 2 and s is a multiple of r, and Lin‐Liu‐Zhu's conjecture is true for .     

Generating Nonisomorphic Quadrangular Embeddings of a Complete Graph

We construct (resp. ) index one current graphs with current group such that the current graphs have different underlying graphs and generate nonisomorphic orientable (resp. nonorientable) quadrangular embeddings of the complete graph , (resp. ).     

A Proof of a Conjecture of Ohba

We prove a conjecture of Ohba that says that every graph G on at most vertices satisfies .     

Large ‐ or ‐Minors in 3‐Connected Graphs

There are numerous results bounding the circumference of certain 3‐connected graphs. There is no good bound on the size of the largest bond (cocircuit) of a 3‐connected graph, however. Oporowski, Oxley, and Thomas (J Combin Theory Ser B 57 (1993), 2, 239–257) proved the following result in 1993. For every positive integer k, there is an integer such that every 3‐connected graph with at least n vertices contains a ‐ or ‐minor. This result implies that the size of the largest bond in a 3‐connected graph grows with the order of the graph. Oporowski et al. obtained a huge function iteratively. In this article, we first improve the above authors' result and provide a significantly smaller and simpler function . We then use the result to obtain a lower bound for the largest bond of a 3‐connected graph by showing that any 3‐connected graph on n vertices has a bond of size at least . In addition, we show the following: Let G be a 3‐connected planar or cubic graph on n vertices. Then for any , G has a ‐minor with , and thus a bond of size at least .     

Extremal Graphs With a Given Number of Perfect Matchings

Let denote the maximum number of edges in a graph having n vertices and exactly p perfect matchings. For fixed p, Dudek and Schmitt showed that for some constant when n is at least some constant . For , they also determined and . For fixed p, we show that the extremal graphs for all n are determined by those with vertices. As a corollary, a computer search determines and for . We also present lower bounds on proving that for (as conjectured by Dudek and Schmitt), and we conjecture an upper bound on . Our structural results are based on Lovász's Cathedral Theorem.     

Partial Online List Coloring of Graphs

For a graph G, let be the maximum number of vertices of G that can be colored whenever each vertex of G is given t permissible colors. Albertson, Grossman, and Haas conjectured that if G is s‐choosable and , then . In this article, we consider the online version of this conjecture. Let be the maximum number of vertices of G that can be colored online whenever each vertex of G is given t permissible colors online. An analog of the above conjecture is the following: if G is online s‐choosable and then . This article generalizes some results concerning partial list coloring to online partial list coloring. We prove that for any positive integers , . As a consequence, if s is a multiple of t, then . We also prove that if G is online s‐choosable and , then and for any , .     

A Combined Logarithmic Bound on the Chromatic Index of Multigraphs

For a multigraph G, the integer round‐up of the fractional chromatic index provides a good general lower bound for the chromatic index . For an upper bound, Kahn 1996 showed that for any real there exists a positive integer N so that whenever . We show that for any multigraph G with order n and at least one edge, ). This gives the following natural generalization of Kahn's result: for any positive reals , there exists a positive integer N so that + c whenever . We also compare the upper bound found here to other leading upper bounds.     

Choosability with Separation of Complete Multipartite Graphs and Hypergraphs

For a hypergraph G and a positive integer s, let be the minimum value of l such that G is L‐colorable from every list L with for each and for all . This parameter was studied by Kratochvíl, Tuza, and Voigt for various kinds of graphs. Using randomized constructions we find the asymptotics of for balanced complete multipartite graphs and for complete k‐partite k‐uniform hypergraphs.     

Connected‐Homomorphism‐Homogeneous Graphs

A relational structure is (connected‐) homogeneous if every isomorphism between finite (connected) substructures extends to an automorphism of the structure. We investigate notions that generalise (connected‐) homogeneity, where ‘isomorphism’ may be replaced by ‘homomorphism’ or ‘monomorphism’ in the definition. In particular, we study the classes of finite connected‐homomorphism‐homogeneous graphs, with the aim of producing classifications. The main result is a classification of the finite graphs, where a graph G is if every homomorphism from a finite connected induced subgraph of G into G extends to an endomorphism of G. The finite (connected‐homogeneous) graphs were classified by Gardiner in 1976, and from this we obtain classifications of the finite and finite graphs. Although not all the classes of finite connected‐homomorphism‐homogeneous graphs are completely characterised, we may still obtain the final hierarchy picture for these classes.     

On the Iterated Biclique Operator

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. The biclique graph of G, denoted by , is the intersection graph of the bicliques of G. We say that a graph G diverges (or converges or is periodic) under an operator F whenever ( for some m, or for some k and , respectively). Given a graph G, the iterated biclique graph of G, denoted by , is the graph obtained by applying the biclique operator k successive times to G. In this article, we study the iterated biclique graph of G. In particular, we classify the different behaviors of when the number of iterations k grows to infinity. That is, we prove that a graph either diverges or converges under the biclique operator. We give a forbidden structure characterization of convergent graphs, which yield a polynomial time algorithm to decide if a given graph diverges or converges. This is in sharp contrast with the situsation for the better known clique operator, where it is not even known if the corresponding problem is decidable. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 181–190, 2013     

Independent Domination in Cubic Graphs

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by , is the minimum cardinality of an independent dominating set. In this article, we show that if is a connected cubic graph of order n that does not have a subgraph isomorphic to K_{2, 3}, then . As a consequence of our main result, we deduce Reed's important result [Combin Probab Comput 5 (1996), 277–295] that if G is a cubic graph of order n, then , where denotes the domination number of G.