Questions tagged [infinite-graphs]

The study of graphs with an infinite number of vertices.

13 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3
votes
0answers
568 views

Is this proof of the four color theorem for infinite graphs legit?

So you got an infinite planar graph $G$. I will prove that it is four colorable. So, construct an infinite number of statements about graphs: The first is "is four colorable" Next, for each vertex $...
2
votes
0answers
28 views

Can the (infinite) graph of a tiling of the plane have no two vertices of the same degree?

I mean for each region to have three or more edges in its boundary. If there's a term for that I'd appreciate a comment as to the term. Another way to state this requirement is that the graph not have ...
2
votes
1answer
52 views

How to think of formal derivation $\Gamma \vdash \phi$ in terms of trees/graphs?

According to my text, a finite set of formulas $\Gamma$ in a given language $L$ is derivable, denoted $\vdash \Gamma$, if $\Gamma$ belongs to the least collection of finite sets of formulas, denoted $...
2
votes
2answers
360 views

Confusion between spectral radius of matrix and spectral radius of the operator

The adjacency matrix $A(G)$ of an infinite undirected graph $G$ is considered as a bounded self-adjoint linear operator $A$ on the Hilbert Space $l^2(G)$ (last section of https://en.wikipedia.org/wiki/...
1
vote
0answers
42 views

Infinite recursive graphs and different ways to build them

Infinite directed graphs (graphs with countably many nodes and edges) have a number of different applications. They can be identified with binary relations, in other words as elements of the power set ...
1
vote
0answers
73 views

Finite Unions of Dendrites

I will ask the main question first, and then give the motivation for this one! The question is a bit specific, but seems to be the most general question to ask after handling some obvious ...
1
vote
0answers
31 views

non-$n$-colorability of an infinite graph and generic partitions of the vertices

I have an infinite graph $G$ and a natural number $n$, and I am interested in the property of $n$-colorability of $G$. I have the naive idea that (1) if almost every partition of the vertices of $...
1
vote
0answers
30 views

How to find a minimal planar covering of a graph

Every graph has a planar covering graph. In particular, the Universal cover, being a tree, will be planar. How do we find a minimal planar covering $P$ graph of a graph $G$? By minimal, I mean that ...
1
vote
0answers
53 views

Infinite Perfect Graphs

A graph $G$ is perfect if every induced subgraph $H$ of $G$ can be coloured with $k$ colours, where $k$ is the size of a largest clique in $H$. The Perfect Graph Theorem (conjectured by Berge and ...
0
votes
0answers
25 views

Brooks' theorem in the infinite

Let $G=(V;E)$ be an infinite graph, with $|V|$ an uncountable cardinal. Suppose that the maximum degree of any $v \in V$ is $\kappa$, where $\kappa \leq |V|$ is an infinite cardinal. Does it follow ...
0
votes
1answer
75 views

How do I apply the infinite Ramsey theorem to graph theory?

The infinite Ramsey theorem reads as such: Theorem. Let $X$ be some infinite set and colour the elements of $X^{(n)}$ (the subsets of $X$ of size $n$) in $c$ different colours. Then there exists ...
-1
votes
1answer
906 views

Is there infinite number between two integers?

With more specific saying, if there is a function that is in continuum from a to b, a and b are real numbers, and bijective to its range, is the number of the function's range infinite? If it is, ...
-2
votes
1answer
82 views

A Question Regarding Representing $\mathscr P$($\omega$) as a Digraph and CH

It is well known that one can represent sets as digraphs. What is the proper digraph representation of $\mathscr P$($\omega$)? I ask this because $\mathscr P$($\omega$) is $\Pi_1$ in the Levy ...