All Questions
Tagged with reference-request graph-theory
453 questions
-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 $...
- 4,195
-2
votes
1
answer
202
views
Natural constructions (not depending on parameters) [closed]
Consider graph clusterings as a prototypical example of (logical) constructions.
Let a clustering of a graph $(V,E)$ be any covering of $V$, i.e. a set $C$ with $\bigcup C = V$.
I am looking for a ...
- 9,720
-3
votes
1
answer
579
views
How does deletion-contraction affect chromatic number? Can it increase chromatic number? [closed]
Question: In graph theory, contracting an edge or deleting an edge are basic operations in many topics such as graph minors or Wagner's theorem on planar graphs. And I'm interested in how these ...
- 419