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-colorings
Search options not deleted
user 384338
Vertex colouring, Edge Colouring, List Colouring, Fractional Chromatic Number and other variants of graph colouring problems are all on topic.
1
vote
0
answers
88
views
Proving $R(n_1+1,n_2+1,\cdots,n_k+1) \leq{n_1+n_2+\cdots+n_k \choose n_1,n_2,\cdots,n_k}$
The following statement is a well-known lemma of Ramsey number.
$$R(m+1,n+1) \leq {m+n \choose m}$$
Now, I want to prove the improvement of the above statement:
$$R(n_1+1,n_2+1,\cdots,n_k+1) \leq{n_1+ …
- 341
1
vote
1
answer
380
views
An equitable edge-coloring of bipartite graphs
In this book (I found it from other references, and it was a nice book to study.), there is an exercise that proving the following two statements.
Every graph $G$ with $m$ edges and maximum degree $k …
- 341
1
vote
1
answer
76
views
Pseudo-replication of a vertex in a perfect graph
Definition of 'replication of $v$' is
Suppose $v \in V(G)$. Replication of $v$ is constructing $G'$ by adding a new vertex $v'$ such that $N_{G'}(v')=N_G(v) \cup \{v\}$.
And the following statement …
- 341
1
vote
1
answer
246
views
If $G$ and $H$ are $k$-critical, then applying Hajós construction to $G$ and $H$ makes $k$-c...
Here is the definition of Hajós construction.
Let $G$ and $H$ be two undirected graphs, $vw$ be an edge of $G$, and $xy$ be an edge of $H$. Then the Hajós construction forms a new graph that combines …
- 341
1
vote
1
answer
173
views
$K_{k,m}$ is $k$-choosable if and only if $m<k^k$
This statement is proved by Vizing and Erdos & Rubin (page 30) independently.
But I cannot find Vizing's paper (It's too old) and Erdos & Rubin's paper only says 'It is easily proved'.
I think it is …
- 341