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 not deleted
user 90655
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
2
answers
564
views
How to translate a graph coloring problem to algebraic or geometric language and solve it?
I want to know whether there are ways to use algebraic methods for solving graph theory problems (graph coloring problems). For example, is it possible to prove the four-color theorem purely with alg …
- 37.7k
4
votes
1
answer
844
views
New edge coloring problem in graph theory
Let $G$ be a simple graph. Consider the following edge coloring:
We are allowed to use repetitive colors on some edges incident to a vertex such that the result does not contain a sequence of length …
CommunityBot
- 1
1
vote
0
answers
94
views
Does anybody know how to prove or disprove the following guess about edge coloring of Hyperg...
Definition. Suppose $H=(V,E)$ is a hypergraph. Call a hyperedge $e=\{v_1,v_2,\dotsc,v_k\}$ a $k$-star if in the 1-skeleton of $H$ there is a copy of $K^{1,k-1}$ whose union equals $e$. (Obviously in t …
CommunityBot
- 1
7
votes
3
answers
683
views
Upper bound for chromatic number of graphs with $\omega(G)\leq\lfloor\frac{\Delta(G)+1}{2}\r...
Let $G$ be a simple graph such that $\omega(G)\leq\lfloor\frac{\Delta(G)+1}{2}\rfloor+1$ where $\Delta(G)$ is the maximal degree of $G$. Is it true that
\begin{equation}
\chi(G)\leq \lfloor\frac{\De …
1
vote
1
answer
164
views
Some question about a new type of graphs
Let $G$ be a simple graph such that some of its vertices are like a fork. i.e. there is vertices $w,x,a,v$ such that edges $[v,w]$ and $[w,a]$ are incident in $w$ and edges $[w,a]$ and $[x,w]$ are …
- 18.4k
1
vote
1
answer
152
views
Edges of every simple graph can be colored with at most $s+1$ color
This question is related to my previous post: New edge coloring problem in graph theory.
Added: Let $G$ be a simple graph. Consider the following edge coloring:
We are allowed to use repetitive co …
- 30.1k
2
votes
1
answer
389
views
Has the Total Coloring Conjecture been proved for complete graphs?
I have a question on the Total Coloring Conjecture in graph theory. This conjecture states that
$$\chi^"(G)\leq \Delta +2,$$
where $\Delta$ is the maximum degree of the graph and $\chi^"(G)$ denotes …
- 6,051
-2
votes
2
answers
120
views
Does $\omega(G)\leq k$ imply $\chi(G)\leq k$ for $n\geq 3$? [closed]
Let $G$ be a simple graph with $n$ vertices. Let $\omega(G)$ and $\chi(G)$ denotes the clique number and chromatic number of $G$ respectively. Then
Does $\omega(G)\leq k$ imply $\chi(G)\leq k$ for …
- 151k
3
votes
1
answer
161
views
Distance relation among points in high-dimensional hypercubes
Let $Q_{4n-1}$ be a unit hypercube of dimension $4n-1$. Has the following statement been proven?
There are $4n$ vertices in $Q_{4n-1}$ such that the distance between each pair of them is $2\sqrt{ …
- 109k
2
votes
3
answers
3k
views
Upper bound on chromatic number for some graphs
I am a beginner in graph theory and I am interested in finding an upper bound for the chromatic number of the following class of graphs:
If two vertices $a$ and $b$ are adjacent in $G$, then th …
- 109k