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 .     

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 .     

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.     

2‐Distance Coloring of Sparse Graphs

For graphs of bounded maximum average degree, we consider the problem of 2‐distance coloring, that is, the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbor receive different colors. We prove that graphs with maximum average degree less than and maximum degree Δ at least 4 are 2‐distance ‐colorable, which is optimal and improves previous results from Dolama and Sopena, and from Borodin et al. We also prove that graphs with maximum average degree less than (resp. , ) and maximum degree Δ at least 5 (resp. 6, 8) are list 2‐distance ‐colorable, which improves previous results from Borodin et al., and from Ivanova. We prove that any graph with maximum average degree m less than and with large enough maximum degree Δ (depending only on m) can be list 2‐distance ‐colored. There exist graphs with arbitrarily large maximum degree and maximum average degree less than 3 that cannot be 2‐distance ‐colored: the question of what happens between and 3 remains open. We prove also that any graph with maximum average degree can be list 2‐distance ‐colored (C depending only on m). It is optimal as there exist graphs with arbitrarily large maximum degree and maximum average degree less than 4 that cannot be 2‐distance colored with less than colors. Most of the above results can be transposed to injective list coloring with one color less.     

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.     

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.     

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 .     

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

Saturation numbers for families of graph subdivisions

For a family of graphs, a graph G is ‐saturated if G contains no member of as a subgraph, but for any edge in , contains some member of as a subgraph. The minimum number of edges in an ‐saturated graph of order n is denoted . A subdivision of a graph H, or an H‐subdivision, is a graph G obtained from H by replacing the edges of H with internally disjoint paths of arbitrary length. We let denote the family of H‐subdivisions, including H itself. In this paper, we study when H is one of or , obtaining several exact results and bounds. In particular, we determine exactly for and show for n sufficiently large that there exists a constant such that . For we show that will suffice, and that this can be improved slightly depending on the value of . We also give an upper bound on for all t and show that . This provides an interesting contrast to a 1937 result of Wagner (Math Ann, 114 (1937), 570–590), who showed that edge‐maximal graphs without a K₅‐minor have at least edges.     

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 .     

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

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

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 .     

On Rooted Packings,Decompositions, and Factors of Graphs

In this article, we study so‐called rooted packings of rooted graphs. This concept is a mutual generalization of the concepts of a vertex packing and an edge packing of a graph. A rooted graph is a pair , where G is a graph and . Two rooted graphs and are isomorphic if there is an isomorphism of the graphs G and H such that S is the image of T in this isomorphism. A rooted graph is a rooted subgraph of a rooted graph if H is a subgraph of G and . By a rooted ‐packing into a rooted graph we mean a collection of rooted subgraphs of isomorphic to such that the sets of edges are pairwise disjoint and the sets are pairwise disjoint. In this article, we concentrate on studying maximum ‐packings when H is a star. We give a complete classification with respect to the computational complexity status of the problems of finding a maximum ‐packing of a rooted graph when H is a star. The most interesting polynomial case is the case when H is the 2‐edge star and S contains the center of the star only. We prove a min–max theorem for ‐packings in this case.     

Neighbor Distinguishing Edge Colorings Via the Combinatorial Nullstellensatz Revisited

Consider a simple graph and its proper edge coloring c with the elements of the set . We say that c is neighbor set distinguishing (or adjacent strong) if for every edge , the set of colors incident with u is distinct from the set of colors incident with v. Let us then consider a stronger requirement and suppose we wish to distinguishing adjacent vertices by sums of their incident colors. In both problems the challenging conjectures presume that such colorings exist for any graph G containing no isolated edges if only . We prove that in both problems is sufficient. The proof is based on the Combinatorial Nullstellensatz, applied in the “sum environment.” In fact the identical bound also holds if we use any set of k real numbers instead of as edge colors, and the same is true in list versions of the both concepts. In particular, we therefore obtain that lists of length ( in fact) are sufficient for planar graphs.     

On a Conjecture on a Laplacian Matrix with Distinct Integral Spectrum

In a paper Fallat et al. (J Graph Theory 50 (2005), 162–174) consider the question of the existence of simple graphs on n vertices whose Laplacian matrix has an integral spectrum consisting of simple eigenvalues only in the range , 0 always being, automatically, one of the eigenvalues. They completely characterize the case when n is one of the eigenvalues, but for the case when n is not, they conjecture that there are no such graphs. In that paper it is shown that, indeed, there are no such graphs for . In this paper we show that the conjecture is true for We actually consider the nonexistence of graphs whose Laplacians are realized by more general spectra , with , , , , and , subject to certain trace conditions. We show that, indeed, for sufficiently large n such graphs do not exist. Our methods are both graph theoretical and algebraic. In certain cases we refine the Cauchy interlacing theorem. Finally, rather than work with Laplacians which have nonpositive off‐Diagonal entries, we transform the problems to the realizability of spectra of nonnegative matrices which we term anti‐Laplacians.     

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.     

Locally Symmetric Graphs of Girth 4

We classify the family of connected, locally symmetric graphs of girth 4 (finite and infinite). They are all regular, with the exception of the complete bipartite graph . There are, up to isomorphism, exactly four such k‐regular graphs for every , one for , two for , and exactly three for every infinite cardinal k. In the last paragraph, we consider locally symmetric graphs of girth >4.