Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with graph-theory
Search options answers only
not deleted
user 43266
Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.
22
votes
Accepted
An unfair marriage lemma
In this answer I sketch an easy proof of your lemma and then give some references.
The easy proof uses Knaster's fixed point theorem:
THEOREM. Let $S$ be any set (finite or infinite) and let $\varphi: …
- 13.4k
21
votes
Accepted
Parity and the Axiom of Choice
The Parity Principle follows from the axiom $\mathbf C_2$ (defined below) which is weaker than the Axiom of Choice. I don't know whether the Parity Principle implies $\mathbf C_2$, but that's another …
- 13.4k
9
votes
Accepted
Is each cover of the plane by lines minimizable?
Unfortunately, you have two questions in one post. The one about $\mathbb R^2$ is too hard for me. The question about $\mathbb Q^2$ seems to have an easy affirmative answer, unless I'm making some dum …
- 13.4k
9
votes
The chromatic number of the union of two graphs
This is a comment, not an answer, but it will be more convenient to post it as an answer. Consider the vertices of $G_n$ as subsets of $[n]=\{1,\dots,n\}$.
Observation 1. $\chi(G_n)\ge\left\lfloor\fra …
- 13.4k
8
votes
Accepted
Graph automorphism that swaps two pairs of nodes
Label the vertices of $C_5$ cyclically: $x,y,z,w,v$. There is a (unique) automorphism that swaps $x$ and $y$, and another (unique) automorphism that swaps $z$ and $w$, but there is no automorphism tha …
- 13.4k
8
votes
Seymour's second neighborhood conjecture for infinite graphs
A "digraph" is a simple digraph without $2$-cycles, i.e., an oriented graph. "Locally finite" means outwards locally finite, i.e., each vertex $x$ has finite outdegree $\deg^+(x)\lt\infty$. If $x,y$ a …
- 13.4k
8
votes
Accepted
Existence of Spanning Tree implies Well Ordering Principle
Let AC denote the axiom of choice. The proof of the implication AC $\implies$ (2) is somewhat nontrivial. Inasmuch as the equivalence AC $\iff$ (1) is quite trivial, it seems unlikely that any "direct …
- 13.4k
7
votes
Accepted
$2n$-regular graphs with maximal chromatic number
Example 1. Let $n=1$, $m=7$. Then $c=3$, and $G=C_3+C_4$ is a $2$-regular graph of order $7$ and chromatic number $3$, but is not isomorphic to $\mathbb Z_7$.
Example 2. Let $n=2$, $m=15$. Then $c=5$ …
- 13.4k
7
votes
Mutually non-isomorphic connected graphs on $\kappa$ points
Let's call a graph asymmetric if it has no nontrivial automorphism. It is stated as Lemma 5 on p. 165 of F. Galvin, G. Hesse, and K. Steffens, On the number of automorphisms of structures, Discrete Ma …
- 13.4k
7
votes
Accepted
Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary rela...
Let $k_n$ be the least integer $k$ such that, for any digraph $D$ of order $n$ and any vertices $x,y\in D$, if there are $x$-$y$ walks of length $1,\dots,k$, then there are $x$-$y$ walks of all positi …
- 13.4k
6
votes
"Gray code" for building teams
Theorem. The graph $G(n,k)$ is Hamiltonian if $n\ge3$ and $0\lt k\lt n$.
Proof. If $k=1$ or $k=n-1$ it's obvious, because $G(n,k)\cong K_n$ in those cases. Now consider the graph $G=G(n,k)$ where $2\l …
- 13.4k
6
votes
Induced subgraphs of any given smaller chromatic number
As noted in a comment by Robert Furber, the original question about induced subgraphs is answered by the following simple counterexample due to F. Galvin, Chromatic Numbers of Subgraphs, Periodica Mat …
- 13.4k
6
votes
Accepted
Clique and chromatic number when removing an edge
Let $H$ be a graph with $\omega(H)=2$ and $\chi(H)=4$, say the Grötzsch graph. Let $G$ be the graph obtained by taking the disjoint union $H\cup K_2\cup K_4$ and adding edges joining both vertices in …
- 13.4k
5
votes
Proof that it's possible to colour all elements in set, that all subsets will be bicolored
Yes. Let $S$ be a family of finite subsets of some linearly ordered set $L.$ Suppose that each member of $S$ has at least two elements, and that no two members of $S$ form a "globally ordered pair". T …
- 13.4k
5
votes
Accepted
Are countable graphs with infinite minimal degree $1$-factorizable?
Yes, any $\aleph_0$-regular graph $G=(V,E)$ is $1$-factorizable. (By "graph" I mean "simple graph" as in the question. Actually a loopless multigraph is OK provided no two vertices are joined by an in …
- 13.4k