On The Chromatic Number Of Pentagon-Free Graphs Of Large Minimum Degree

We prove that, for each fixed real number c > 0, the pentagon-free graphs of minimum degree at least cn (where n is the number of vertices) have bounded chromatic number. This problem was raised by Erdős and Simonovits in 1973. A similar result holds for any other fixed odd cycle, except the triangle for which there is no such result for c<1/3.     

Circular Chromatic Number and Mycielski Graphs

As a natural generalization of graph coloring, Vince introduced the star chromatic number of a graph G and denoted it by ^*(G). Later, Zhu called it circular chromatic number and denoted it by _c(G). Let (G) be the chromatic number of G. In this paper, it is shown that if the complement of G is non-hamiltonian, then _c(G)=(G). Denote by M(G) the Mycielski graph of G. Recursively define M^m(G)=M(M^m–1(G)). It was conjectured that if mn–2, then _c(M^m(K_n))=(M^m(K_n)). Suppose that G is a graph on n vertices. We prove that if , then _c(M(G))=(M(G)). Let S be the set of vertices of degree n–1 in G. It is proved that if |S| 3, then _c(M(G))=(M(G)), and if |S| 5, then _c(M²(G))=(M²(G)), which implies the known results of Chang, Huang, and Zhu that if n3, _c(M(K_n))=(M(K_n)), and if n5, then _c(M²(K_n))=(M²(K_n)).* Research supported by Grants from National Science Foundation of China and Chinese Academy of Sciences.     

Hypergraph Extension Of The Alon-Tarsi List Coloring Theorem

A circulation in a digraph is a spanning subgraph with indegree equal to outdegree at each vertex. Alon and Tarsi proved that a graph is d-choosable when it has an orientation that has no vertex of outdegree at least d and has the property that the numbers of circulations with even-sized and odd-sized edge sets differ. We generalize this to k-uniform hypergraphs for prime k. We use a hypergraph polynomial and a notion of hypergraph orientation defined by choosing a source vertex from each edge.* Project sponsored by the National Security Agency under Grant Number MDA904-03-1-0037. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation herein.     

On the Chromatic Number of Triangle-Free Graphs of Large Minimum Degree

We prove that, for each xed real number c > 1/3, the triangle-free graphs of minimum degree at least cn (where n is the number of vertices) have bounded chromatic number. This problem was raised by Erds and Simonovits in 1973 who pointed out that there is no such result for c < 1/3.     

Some Remarks on the Simultaneous Chromatic Number

We present several partial results, variants, and consistency results concerning the following (as yet unsolved) conjecture. If X is a graph on the ground set V with then X has an edge coloring F with colors such that if V is decomposed into parts then there is one in which F assumes all values.Due to some unfortunate misunderstandings, this paper appeared much later than we expected.* Research partially supported by NSF grants DMS-9704477 and DMS-0072560. Research partially supported by Hungarian National Research Grant T 032455.     

Graphs Whose Circular Chromatic Number Equals the Chromatic Number

Received: October 24, 1997     

The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity

On Circular Flows Of Graphs

A sufficient condition for graphs with circular flow index less than 4 is found in this paper. In particular, we give a simple proof of a result obtained by Galluccio and Goddyn (Combinatorica, 2002), and obtain a larger family of such graphs. * Partially supported by the National Security Agency under Grants MDA904-01-1-0022.     

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 .     

Colouring games based on autotopisms of Latin hyper-rectangles

Abstract

Every partial colouring of a Hamming graph is uniquely related to a partial Latin hyper-rectangle. In this paper we introduce the Θ-stabilized (a, b)-colouring game for Hamming graphs, a variant of the (a, b)-colouring game so that each move must respect a given autotopism Θ of the resulting partial Latin hyperrectangle. We examine the complexity of this variant by means of its chromatic number. We focus in particular on the bi-dimensional case, for which the game is played on the Cartesian product of two complete graphs, and also on the hypercube case.     

Local Chromatic Number, KY Fan's Theorem, And Circular Colorings

The local chromatic number of a graph was introduced in [14]. It is in between the chromatic and fractional chromatic numbers. This motivates the study of the local chromatic number of graphs for which these quantities are far apart. Such graphs include Kneser graphs, their vertex color-critical subgraphs, the Schrijver (or stable Kneser) graphs; Mycielski graphs, and their generalizations; and Borsuk graphs. We give more or less tight bounds for the local chromatic number of many of these graphs. We use an old topological result of Ky Fan [17] which generalizes the Borsuk–Ulam theorem. It implies the existence of a multicolored copy of the complete bipartite graph K_{⌈t/2⌉,⌊t/2⌋} in every proper coloring of many graphs whose chromatic number t is determined via a topological argument. (This was in particular noted for Kneser graphs by Ky Fan [18].) This yields a lower bound of ⌈t/2⌉ + 1 for the local chromatic number of these graphs. We show this bound to be tight or almost tight in many cases. As another consequence of the above we prove that the graphs considered here have equal circular and ordinary chromatic numbers if the latter is even. This partially proves a conjecture of Johnson, Holroyd, and Stahl and was independently attained by F. Meunier [42]. We also show that odd chromatic Schrijver graphs behave differently, their circular chromatic number can be arbitrarily close to the other extreme. * Research partially supported by the Hungarian Foundation for Scientific Research Grant (OTKA) Nos. T037846, T046376, AT048826, and NK62321. † Research partially supported by the NSERC grant 611470 and the Hungarian Foundation for Scientific Research Grant (OTKA) Nos. T037846, T046234, AT048826, and NK62321.     

A Bound on the Total Chromatic Number

. The proof is probabilistic. Received: November 26, 1996     

On the Toughness of a Graph

Abstract

In this paper, general results on the toughness of a graph are considered. Firstly the link between toughness and connectivity is explored and then results linking toughness and the parameters binding number and integrity are given. Further, the toughness of product graphs is discussed including general results for the lexicographic product. The paper concludes with some observations on toughness and hamiltoni-city.     

On The Number Of Sets Of Cycle Lengths

A set S of integers is called a cycle set on {1, 2, . . .,n} if there exists a graph G on n vertices such that the set of lengths of cycles in G is S. Erds conjectured that the number of cycle sets on {1, 2, . . .,n} is o(2 ⁿ ). In this paper, we verify this conjecture by proving that there exists an absolute constant c 0.1 such that the number of cycle sets on {1, 2, . . .,n} is .     

Graph Connectivity After Path Removal

Let G be a graph and u, v be two distinct vertices of G. A u—v path P is called nonseparating if G—V(P) is connected. The purpose of this paper is to study the number of nonseparating u—v path for two arbitrary vertices u and v of a given graph. For a positive integer k, we will show that there is a minimum integer (k) so that if G is an (k)-connected graph and u and v are two arbitrary vertices in G, then there exist k vertex disjoint paths P ₁[u,v], P ₂[u,v], . . ., P _k [u,v], such that G—V (P _i [u,v]) is connected for every i (i = 1, 2, ..., k). In fact, we will prove that (k) 22k+2. It is known that (1) = 3.. A result of Tutte showed that (2) = 3. We show that (3) = 6. In addition, we prove that if G is a 5-connected graph, then for every pair of vertices u and v there exists a path P[u, v] such that G—V(P[u, v]) is 2-connected.* Supported by NSF grant No. DMS-0070059 Supported by ONR grant N00014-97-1-0499 Supported by NSF grant No. 9531824     

The Number Of Orientations Having No Fixed Tournament

Let T be a fixed tournament on k vertices. Let D(n,T ) denote the maximum number of orientations of an n-vertex graph that have no copy of T. We prove that for all sufficiently (very) large n, where t_k−1(n) is the maximum possible number of edges of a graphon n vertices with no K_k, (determined by Turán’s Theorem). The proof is based on a directed version of Szemerédi’s regularity lemma together with some additional ideas and tools from Extremal Graph Theory, and provides an example of a precise result proved by applying this lemma. For the two possible tournaments with three vertices we obtain separate proofs that avoid the use of the regularity lemma and therefore show that in these cases already holds for (relatively) small values of n. * Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.     

Graph homomorphisms and nodal domains

In this paper, we derive some necessary spectral conditions for the existence of graph homomorphisms in which we also consider some parameters related to the corresponding eigenspaces such as nodal domains. In this approach, we consider the combinatorial Laplacian and co-Laplacian as well as the adjacency matrix. Also, we present some applications in graph decompositions where we prove a general version of Fisher’s inequality for G-designs.     

Graph colourings and solutions of systems of equations over finite fields

A congruence (p is a prime) is said to be strong homogeneous if it has the form

     

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.     

On the Number of Latin Squares

We (1) determine the number of Latin rectangles with 11 columns and each possible number of rows, including the Latin squares of order 11, (2) answer some questions of Alter by showing that the number of reduced Latin squares of order n is divisible by f! where f is a particular integer close to (3) provide a formula for the number of Latin squares in terms of permanents of (+1, −1)-matrices, (4) find the extremal values for the number of 1-factorisations of k-regular bipartite graphs on 2n vertices whenever 1 ≤ k ≤ n ≤ 11, (5) show that the proportion of Latin squares with a non-trivial symmetry group tends quickly to zero as the order increases. Received September 3, 2004