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.     

Circular Chromatic Indices of Regular Graphs

The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are adjacent. It is known that for any , there is a 3‐regular simple graph G with . This article proves the following results: Assume is an odd integer. For any , there is an n‐regular simple graph G with . For any , there is an n‐regular multigraph G with .     

Destroying Noncomplete Regular Components in Graph Partitions

We prove that if G is a graph and such that then can be partitioned into sets such that and contains no noncomplete ‐regular components for each . In particular, the vertex set of any graph G can be partitioned into sets, each of which induces a disjoint union of triangles and paths.     

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.     

Toughness and Vertex Degrees

We study theorems giving sufficient conditions on the vertex degrees of a graph G to guarantee G is t‐tough. We first give a best monotone theorem when , but then show that for any integer , a best monotone theorem for requires at least nonredundant conditions, where grows superpolynomially as . When , we give an additional, simple theorem for G to be t‐tough, in terms of its vertex degrees.     

Limits of Near‐Coloring of Sparse Graphs

Let be nonnegative integers. A graph G is ‐colorable if its vertex set can be partitioned into sets such that the graph induced by has maximum degree at most d for , while the graph induced by is an edgeless graph for . In this article, we give two real‐valued functions and such that any graph with maximum average degree at most is ‐colorable, and there exist non‐‐colorable graphs with average degree at most . Both these functions converge (from below) to when d tends to infinity. This implies that allowing a color to be d‐improper (i.e., of type ) even for a large degree d increases the maximum average degree that guarantees the existence of a valid coloring only by 1. Using a color of type (even with a very large degree d) is somehow less powerful than using two colors of type (two stable sets).     

Average Degree in Graph Powers

The kth power of a simple graph G, denoted by , is the graph with vertex set where two vertices are adjacent if they are within distance k in G. We are interested in finding lower bounds on the average degree of . Here we prove that if G is connected with minimum degree and , then G⁴ has average degree at least . We also prove that if G is a connected d‐regular graph on n vertices with diameter at least , then the average degree of is at least Both these results are shown to be essentially best possible; the second is best possible even when is arbitrarily large.     

On the Circular Chromatic Number of Graph Powers

This article intends to study some functors from the category of graphs to itself such that, for any graph G, the circular chromatic number of is determined by that of G. In this regard, we investigate some coloring properties of graph powers. We show that provided that . As a consequence, we show that if , then . In particular, and has no subgraph with circular chromatic number equal to . This provides a negative answer to a question asked in (X. Zhu, Discrete Math, 229(1–3) (2001), 371–410). Moreover, we investigate the nth multichromatic number of subdivision graphs. Also, we present an upper bound for the fractional chromatic number of subdivision graphs. Precisely, we show that .     

The Degree‐Diameter Problem for Claw‐Free Graphs and Hypergraphs

We study the degree‐diameter problem for claw‐free graphs and 2‐regular hypergraphs. Let be the largest order of a claw‐free graph of maximum degree Δ and diameter D. We show that , where , for any D and any even . So for claw‐free graphs, the well‐known Moore bound can be strengthened considerably. We further show that for with (mod 4). We also give an upper bound on the order of ‐free graphs of given maximum degree and diameter for . We prove similar results for the hypergraph version of the degree‐diameter problem. The hypergraph Moore bound states that the order of a hypergraph of maximum degree Δ, rank k, and diameter D is at most . For 2‐regular hypergraph of rank and any diameter D, we improve this bound to , where . Our construction of claw‐free graphs of diameter 2 yields a similar result for hypergraphs of diameter 2, degree 2, and any even rank .     

Biembedding a Steiner Triple System With a Hamilton Cycle Decomposition of a Complete Graph

We construct a face two‐colourable, blue and green say, embedding of the complete graph in a nonorientable surface in which there are blue faces each of which have a hamilton cycle as their facial walk and green faces each of which have a triangle as their facial walk; equivalently a biembedding of a Steiner triple system of order n with a hamilton cycle decomposition of , for all and . Using a variant of this construction, we establish the minimum genus of nonorientable embeddings of the graph , for where and .     

Orientable Hamilton Cycle Embeddings of Complete Tripartite Graphs II: Voltage Graph Constructions and Applications

In an earlier article the authors constructed a hamilton cycle embedding of in a nonorientable surface for all and then used these embeddings to determine the genus of some large families of graphs. In this two‐part series, we extend those results to orientable surfaces for all . In part II, a voltage graph construction is presented for building embeddings of the complete tripartite graph on an orientable surface such that the boundary of every face is a hamilton cycle. This construction works for all such that p is prime, completing the proof started by part I (which covers the case ) that there exists an orientable hamilton cycle embedding of for all , . These embeddings are then used to determine the genus of several families of graphs, notably for and, in some cases, for .     

Eigenvalues of ‐Free Graphs and the Connectivity of Their Independence Complexes

Let G be a graph on n vertices, with maximal degree d, and not containing as an induced subgraph. We prove:

• 1.
• 2.

Here is the maximal eigenvalue of the Laplacian of G, is the independence complex of G, and denotes the topological connectivity of a complex plus 2. These results provide improved bounds for the existence of independent transversals in ‐free graphs.     

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. ).     

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     

Maximizing H‐Colorings of a Regular Graph

For graphs G and H, a homomorphism from G to H, or H‐coloring of G, is an adjacency preserving map from the vertex set of G to the vertex set of H. Our concern in this article is the maximum number of H‐colorings admitted by an n‐vertex, d‐regular graph, for each H. Specifically, writing for the number of H‐colorings admitted by G, we conjecture that for any simple finite graph H (perhaps with loops) and any simple finite n‐vertex, d‐regular, loopless graph G, we have where is the complete bipartite graph with d vertices in each partition class, and is the complete graph on vertices.Results of Zhao confirm this conjecture for some choices of H for which the maximum is achieved by . Here, we exhibit for the first time infinitely many nontrivial triples for which the conjecture is true and for which the maximum is achieved by .We also give sharp estimates for and in terms of some structural parameters of H. This allows us to characterize those H for which is eventually (for all sufficiently large d) larger than and those for which it is eventually smaller, and to show that this dichotomy covers all nontrivial H. Our estimates also allow us to obtain asymptotic evidence for the conjecture in the following form. For fixed H, for all d‐regular G, we have where as . More precise results are obtained in some special cases.     

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 .     

Total Vertex Irregularity Strength of Dense Graphs

Consider a graph of minimum degree δ and order n. Its total vertex irregularity strength is the smallest integer k for which one can find a weighting such that for every pair of vertices of G. We prove that the total vertex irregularity strength of graphs with is bounded from above by . One of the cornerstones of the proof is a random ordering of the vertices generated by order statistics.