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 17581
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.
4
votes
Accepted
Different graphs with the same open neighborhood hypergraph
The answer to the first question is positive. Consider two graphs on eight vertices each consisting of two disjoint 4-cycles: the first one's cycles are $abcd$ and $efgh$, the second's ones are $afch$ …
- 23.7k
3
votes
Accepted
A question about a specific partition of a graph
Denote $d_A(v)=|N_G(v)\cap A|$, $d_B(v)=|N_G(v)\cap B|$. Set $S_A=\{(a,b)\in A\times B\colon N_G(a)\cap N_G(b)\cap A\neq\varnothing\}$ and $S_B=\{(a,b)\in A\times B\colon N_G(a)\cap N_G(b)\cap B\neq\v …
- 23.7k
2
votes
Isomorphic Hadwiger graphs
$\def\Hadw{\mathop{\rm Hadw}}$If it is not a mauvais ton, I would like to add an easier proof found independently by Sergey Dolgikh and Marat Abdrakhmanov (we used this fact as a contest problem). We …
- 23.7k
1
vote
the minimum possible value of the order of a graph G which is a finite union of N-order comp...
In a beautiful paper A. Hajnal obtained the following Lemma.
Lemma. Let $G$ be a graph on $n$ vertices containing no $(k+1)$-clique. Then all $k$-cliques in $G$ have at least $2k-n$ common vertices.
…
- 23.7k
5
votes
Accepted
Isomorphic Hadwiger graphs
$\def\Hadw{\mathop{\rm Hadw}}$This is true for finite graphs, and false for (not necessarily connected) infinite graphs. Right now I do not know what happens for infinite connected graphs.
1. Each co …
- 23.7k
3
votes
Accepted
n-cube connectivity problem
Every vertex removed from the $k$th layer prohibits $k!(n-k)!\leq (n-1)!$ paths. Thus, if $n$ removed verices prohibit all $n!$ paths, then each of them prohibits exactly $(n-1)!$ paths, and the sets …
- 23.7k
1
vote
Critical graphs and endomorphisms
Say that a graph is strongly critical if deletion of any vertex or edge decreases its chromatic number.
Take any two nonisomorphic $k$-strongly critical graphs $G$ and $H$ with the same number of ver …
- 23.7k
0
votes
3-coloring of specific planar graphs
It seems that the statement is true even without the assumption that the graph is planar. Actually, let $T$ be a tree which is not a star, and let $C$ be a cycle on all the leaves of $T$; then the gra …
- 23.7k
3
votes
Accepted
Bound on the largest minimal vertex cover in a graph
Take a complete graph $K_d$. For every its vertex $u$, take $d$ more vertices connected just to $u$. We get $d(d+1)$ vertices in total.
Every minimal vertex cover contains all but one vertices of $K_ …
- 23.7k
3
votes
Accepted
Total chromatic number and bipartite graphs
Let $a=\chi(G)\geq 3$ and $b=\chi'(G)$. Paint the vertices in $a$ colors and edges in $b$ colors properly. Now choose one color class of edges. Repaint each of them into one of the first $a$ colors, d …
- 23.7k
2
votes
Accepted
Degree of neighbors in a simple graph (friendship paradox variant)
Well, a modification of the previous example works. Take some number $n$ such that there are proper divisors $a\mid n$ and $b\mid n+1$ with $a>b$. Let $V=V_1\sqcup V_2$, with $|V_1|=n$, $|V_2|=n+1$. T …
- 23.7k
6
votes
Smallest odd cycle in a non-bipartite graph
I care only about linear term in the answer, relaxing an additive constant. However, for $n=12k+11$ I show the tight answer.
An example I told in a comment was slightly suboptimal. An optimal one is …
- 23.7k
6
votes
Accepted
Do graphs with $\omega(G) = \chi(G)$ grow "common" as $|V|$ grows large?
I would say that this limit is zero. Most of the graphs on $n$ vertices have $\sim n^2/4$ edges. For such graph, the expected number of complete subgraphs of size $k\sim2\log_2n$ is
$$
{n\choose k}\ …
- 23.7k
7
votes
Accepted
Majority coloring for directed graphs
Let me answer Question 2. The answer is in negative: there exists an upper bound for majority coloring numbers of all tournaments. I will not care about the sharpness of the bound.
Let $G$ be a tourn …
- 23.7k
5
votes
Which paths in a graph are orthogonal to all cycles?
EDIT Take te multiset of all edges of $\gamma$; if it contains a pair of inverse edges, remove it, and repeat this while possible. If the resulting multiset is empty, then $c(\gamma)=0$, otherwise we …
- 23.7k