Finding the chromatic number of a graph with biconnected components

[Superyoshiom]

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]

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.,