I Finding the chromatic number of a graph with biconnected components

Our problem involves a graph G that is simple and connected, where every biconnected component is a cycle that has at least four vertices in it. The maximum number of components we can get from removing a cut vertex is 4, and we are asked to find tight bounds on the chromatic number of G.

My idea was to take the cycles and then do cases for whether they are even or odd:

1) Even cycle - in an even cycle we can have have at least two colors if we alternate colors for the vertices. For every vertex that is neighboring the biconnected component, then, we wouldn't need to add new colors since we just make them the alternate of whatever they are next to. So we'd only need a chromatic number of 2 here.

2) Odd cycle - similar idea, but we'd need three vertices for a cycle so our chromatic number of 3.

So my final answr would be 2<=X(G)=3, but this doesn't make that much sense to me, and I didn't really need to use the information about the cut vertices. I'm not sure where to proceed from here so any help would be greatly appreciated.
 

andrewkirk

Science Advisor
Homework Helper
Insights Author
Gold Member
3,738
1,359
I believe your bounds of 2 and 3 are correct, and that the premise about the cut vertex is not needed. To be sure, we'd need to make the proof more rigorous than what is above though.

I believe the premises, excluding the cut vertex one, imply that the graph must consist of cycles of length at least four, that can be arranged in a non-recombining tree. Each biconnected component (cycle) of the graph is a node of that tree. Each "edge" of the tree is a sequence of one or more serially-connected cut vertices (of the original graph). One such sequence in the original graph may manifest as more than one edge in the tree. The 'cut vertex' premise implies the sequence cannot manifest as more than four tree edges. But that has no impact on the colouring bounds.

If that is the case, it is easy to see that your bounds hold. But we need to make rigorous the proof that the graph does indeed have that form.,
 

Want to reply to this thread?

"Finding the chromatic number of a graph with biconnected components" 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