Finding the chromatic number of a graph with biconnected components

Click For Summary
SUMMARY

The discussion focuses on determining the chromatic number of a simple, connected graph G, where each biconnected component is a cycle with at least four vertices. The analysis concludes that for even cycles, the chromatic number is 2, while for odd cycles, it is 3, leading to the bounds of 2 ≤ X(G) ≤ 3. The relevance of cut vertices in this context is deemed unnecessary for establishing these bounds, although a more rigorous proof is required to confirm the graph's structure as a non-recombining tree of cycles.

PREREQUISITES
  • Understanding of graph theory concepts, specifically biconnected components.
  • Knowledge of chromatic numbers and their implications in graph coloring.
  • Familiarity with cycle properties in graphs, including even and odd cycles.
  • Basic proof techniques in mathematics to establish rigorous arguments.
NEXT STEPS
  • Study the properties of biconnected components in graph theory.
  • Learn about chromatic polynomials and their applications in graph coloring.
  • Explore the concept of non-recombining trees and their relevance to graph structures.
  • Investigate proof techniques for establishing bounds in combinatorial problems.
USEFUL FOR

Mathematicians, computer scientists, and students interested in graph theory, particularly those focusing on graph coloring and structural properties of graphs.

Superyoshiom
Messages
29
Reaction score
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.
 
Mathematics news on Phys.org
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.,
 

Similar threads

Undergrad Question regarding degrees of a graph and its biconnected components
  • · Replies 34 ·
2
Replies
34
Views
6K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
3K
Graduate About a natural extension of Collatz conjecture
  • · Replies 3 ·
Replies
3
Views
905
Undergrad Finding the dependence of maximum vertex degree on k-colorability
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Spatial graphs and their chromatic number
  • · Replies 12 ·
Replies
12
Views
7K
Undergrad The number of intersection graphs of ##n## convex sets in the plane
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad Edge connectivity of a graph given the number of edge disjoint paths
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Find Smallest Subtree of G w/ Nodes from S
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Finding if a subgraph of a minimal non-planar graph is maximal planar
  • · Replies 1 ·
Replies
1
Views
2K
MHB A Subset of a Graph with No Perfect Matching
  • · Replies 1 ·
Replies
1
Views
2K