- 29

- 0

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