I Finding the dependence of maximum vertex degree on k-colorability

How do we describe a construction of a 2-colorable graph where the degree of every vertex is greater than or equal to (|V|-1)/2? Based on that, what can be said about the dependence of maximum vertex-degree on k-colorability of a graph?

My first thought is that in order for a vertex to connect to every single other vertex on a graph, it's degree would have to be |V|-1. But since we're looking at half of that in (|V|-1)/2, it would only be connected to half the vertices in the graph, so if this was the case for all vertices in G we'd be constructing a 2-colorable bipartite graph (is my thought).

I'm not too sure how to deal with the second part, however. I know that in a graph there can be n different colors for k given n vertices in a row and we need to add colors whenever there are adjacent vertices, but I can't figure out how the maximum vertex-degree in particular effects how many colors we can use for a graph.
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,237
4,557
we'd be constructing a 2-colorable bipartite graph
Right, but you can be a bit more precise. Since it is 2-colorable, it is bipartite. What are the possibilities for the numbers in each part? Does it need to be complete?
Based on that, what can be said about the dependence of maximum vertex-degree
The question seems garbled. The first part concerned the minimum vertex degree, (n-1)/2, not the maximum.
As for the first part, you can cluster the vertices according to colour, with each vertex only allowed to connect into other clusters. But if you make one cluster consist of a single vertex then it can have degree n-1, so it doesn’t say anything about the max vertex degree. I would interpret it as asking how high the minimum vertex degree can be.
 

Want to reply to this thread?

"Finding the dependence of maximum vertex degree on k-colorability" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top