The list-chromatic number of infinite graphs

We investigate the list-chromatic number of infinite graphs. It is easy to see that Chr(X) ≤ List(X) ≤ Col(X) for each graph X. It is consistent that List(X) = Col(X) holds for every graph with Col(X) infinite. It is also consistent that for graphs of cardinality ? ₁, List(X) is countable iff Chr(X) is countable.     

The fractional chromatic number of infinite graphs

The fractional chromatic number of a graph G is the infimum of the total weight that can be assigned to the independent sets of G in such a way that, for each vertex v of G, the sum of the weights of the independent sets containing v is at least 1. In this note we give a graph a graph whose fractional chromatic number is strictly greater than the supremum of the fractional chromatic numbers of its finite subgraphs. This answers a question of Zhu. We also give some grphs for which the fractional chromatic number is not attined, answering another of Zhu. © 1995 John Wiley & Sons, Inc.     

The Hadwiger number of infinite vertex-transitive graphs

We prove that every infinite, locally finite 3-connected, almost 4-connected, almost transitive, nonplanar graph, which contains infinitely many pairwise disjoint infinite paths belonging to the same end, can be contracted into an infinite complete graph. This implies that every infinite, locally finite, connected, nonplanar vertex-transitive graph with only one end can be contracted into an infinite complete graph. This problem was raised by L. Babai.     

On the Hadwiger number of infinite graphs

LetX be a connected graph with bounded valency and at least one thick end. We show that the existence of certain subgroups of the automorphism group ofX always implies thatX has infinite Hadwiger number.     

The chromatic number of infinite graphs — A survey

We survey some old and new results on the chromatic number of infinite graphs.     

On infinite graphs with a specified number of colorings

In this paper we construct a planar graph of degree four which admits exactly N_u 3-colorings, we prove that such a graph must have degree at least four, and we consider various generalizations. We first allow our graph to have either one or two vertices of infinite degree and/or to admit only finitely many colorings and we note how this effects the degrees of the remaining vertices. We next consider n-colorings for n>3, and we construct graphs which we conjecture (but cannot prove) are of minimal degree. Finally, we consider nondenumerable graphs, and for every 3 <n<ω and every infinite cardinal k we construct a graph of cardinality k which admits exactly kn-colorings. We also show that the number of n-colorings of a denumerable graph can never be strictly between N_u and 2^N_u and that an appropriate generalization holds for at least certain nondenumerable graphs.     

Decomposition of infinite eulerian graphs with a small number of vertices of infinite degree

We consider the question whether an infinite eulerian graph has a decomposition into circuits and rays if the graph has only finitely many, say n, vertices of infinite degree, and only finitely many finite components after the removal of the vertices of infinite degree. It is known that the answer is affirmative for n2 and negative for n4. We settle the remaining case n=3, showing that a decomposition into circuits and rays also exists in this case.     

The cover-index of infinite graphs

We show that the cover-index of an infinite graph can be expressed in terms of colouring properties of its finite subgraphs when the minimum degree of the graph is finite. We prove that every simple graph with infinite minimum degree contains a tree which is regular of degree and use this to prove that every graph with minimum degree can be decomposed into mutually edge-disjoint spanning subgraphs without ioslated vertices. In particular, the cover-index of a graph equals the minimum degree, when this is infinite.     

An infinite family of subcubic graphs with unbounded packing chromatic number

Recently, Balogh et al. (2018) answered in negative the question that was posed in several earlier papers whether the packing chromatic number is bounded in the class of graphs with maximum degree 3. In this note, we present an explicit infinite family of subcubic graphs with unbounded packing chromatic number.     

The spectrum of infinite regular line graphs

Let be an infinite -regular graph and its line graph. We consider discrete Laplacians on and , and show the exact relation between the spectrum of and that of . Our method is also applicable to -semiregular graphs, subdivision graphs and para-line graphs.

     

Duality of infinite graphs

Some basic results on duality of infinite graphs are established and it is proven that a block has a dual graph if and only if it is planar and any two vertices are separated by a finite edge cut. Also, the graphs having predual graphs are characterized completely and it is shown that if $\text{G}{}^1$ is a dual and predual graph of G, then G and $\text{G}{}^1$ can be represented as geometric dual graphs. The uniqueness of dual graphs is investigated, in particular, Whitney's 2-isomorphism theorem is extended to infinite graphs. Finally, infinite minimal cuts in dual graphs are studied and the characterization (in terms of planarity and separation properties) of the graphs having dual graphs satisfying conditions on the infinite cuts, as well, is included.     

The reconstruction problem for certain infinite graphs

We are concerned with the notion of the degree-type (D _G ⁱ )_i∈ω of a graphG, whereD _G ⁱ is defined to be the number of vertices inG with degreei. In the first section the following results are proven:

1. IfG is a connected, locally finite, countably infinite graph such that there exists ani so thatD _G ⁱ andD _G ⁱ⁺¹ are both finite and different from 0, thenG is reconstructible.
2. Locally finite, countably infinite graphsG, for which infinitely manyD _G ⁱ are different from 0 but only finitely manyD _G ⁱ are infinite, are reconstructible.

In the second section we give some results about the reconstructibility of certain locally finite countably infinite interval graphs and show that a reconstruction of a planar, infinite graph has to be planar too.     

Note on the reconstruction of infinite graphs with a fixed finite number of components

For every positive integer c, we construct a pair G_c, H_c of infinite, nonisomorphic graphs both having exactly c components such that G_c and H_c are hypomorphic, i.e., G_c and H_c have the same families of vertex-deleted subgraphs. This solves a problem of Bondy and Hemminger. Furthermore, the pair G₁, H₁ is an example for a pair of non-isomorphic, hypomorphic, connected graphs also having connected complements—a property not shared by any of the previously known counterexamples to the reconstruction conjecture for infinite graphs.     

Note on infinite graphs

Some relations between the number of nodes and edges and the degrees of the nodes in infinite graphs are obtained. The structure of infinite connected graphs which have no- ∞ trails is investigated with the help of these. It is shown, for example, that any such graph G has |G| nodes of odd degree.     

Matchings on infinite graphs

Elek and Lippner (Proc. Am. Math. Soc. 138(8), 2939–2947, 2010) showed that the convergence of a sequence of bounded-degree graphs implies the existence of a limit for the proportion of vertices covered by a maximum matching. We provide a characterization of the limiting parameter via a local recursion defined directly on the limit of the graph sequence. Interestingly, the recursion may admit multiple solutions, implying non-trivial long-range dependencies between the covered vertices. We overcome this lack of correlation decay by introducing a perturbative parameter (temperature), which we let progressively go to zero. This allows us to uniquely identify the correct solution. In the important case where the graph limit is a unimodular Galton–Watson tree, the recursion simplifies into a distributional equation that can be solved explicitly, leading to a new asymptotic formula that considerably extends the well-known one by Karp and Sipser for Erd?s-Rényi random graphs.     

Invariant Hamming graphs in infinite quasi-median graphs

It is shown that a quasi-median graph G without isometric infinite paths contains a Hamming graph (i.e., a cartesian product of complete graphs) which is invariant under any automorphism of G, and moreover if G has no infinite path, then any contraction of G into itself stabilizes a finite Hamming graph.     

The complexity of a class of infinite graphs

IfG _k is the family of countable graphs with nok vertex (or edge) disjoint circuits (1<k<) then there is a countableG _k G _k such that every member ofG _k is an (induced) subgraph of some member ofG _k , but no finiteG _k suffices.     

Strongly perfect infinite graphs

An infinite graph G is calledstrongly perfect if each induced subgraph ofG has a coloring (C _i :i ∈I) and a clique meeting each colorC _i . A conjecture of the first author and V. Korman is that a perfect graph with no infinite independent set is strongly perfect. We prove the conjecture for chordal graphs and for their complements. The research was begun at the Sonderforschungsbereich 343 at Bielefeld University and supported by the Fund for the Promotion of Research at the Technion.     

The binding number of line graphs and total graphs

D.R. Woodall [7] introduced the concept of the binding number of a graphG, bind (G), and proved that bind(G)≦(|V(G)|−1)/(|V(G)|−ρ(G)). In this paper, some properties of a graph with bind(G)=(|V(G)|−1)/(|V(G)|−ρ(G)) are given, and the binding number of some line graphs and total graphs are determined.