More graph theory

In summary, the conversation discusses various ideas for proving the existence of a triangle-free k-chromatic graph for any positive integer k, as well as proving the optimality of a greedy coloring algorithm on the complement graph of a chordal graph when using a reverse simplicial ordering. Suggestions for using induction and the subgraph argument are mentioned, but the messy nature of graph theory proofs is also acknowledged."
  • #1

vshiro

does anyone have an idea on proving that there is a triangle-free k-chromatic graph for every positive integer k?

or, how to prove that given a simplicial ordering on a chordal graph G, running the greedy coloring algorithm on the reverse order gives the optimal coloring on the complement graph?

one might think to use induction but it's all very messy and ecchhh
 
Mathematics news on Phys.org
  • #2
Usually the proofs in Graph theory have a quite messy appearence. I suggest you to have a look on Harary in order to see how boring it can be. And then I suggest that, if the assertions are true (I have not meditated about it), then try to use the subgraph argument, i.e., try to construct for the arbitrary case a subgraph that contradicts the assumption. See for example the Kuratowski theorem about planarity to see what I mean.
 
  • #3


There are a few different approaches that could potentially be used to prove the existence of a triangle-free k-chromatic graph for any positive integer k. One possibility is to use the probabilistic method, which involves constructing a random graph and showing that the probability of it being triangle-free and k-chromatic approaches 1 as the number of vertices increases. Another approach could be to use a constructive proof, where you actually build the graph step by step and show that each step maintains the desired properties. Induction could also be a potential method, as you mentioned, but as you pointed out, it could be a messy and complex approach. It may be helpful to explore other techniques or approaches to see if they provide a more elegant solution.

For the second question about proving the optimality of the greedy coloring algorithm on the complement graph, it may be helpful to look at the properties of chordal graphs and how they relate to the greedy coloring algorithm. For example, a chordal graph has a perfect elimination ordering, which guarantees that the greedy coloring algorithm will produce an optimal coloring. Additionally, the complement graph of a chordal graph is also chordal, so there may be a way to use this property to prove the optimality of the greedy coloring algorithm on the complement graph. Again, exploring different approaches and techniques may lead to a more efficient and elegant solution.
 

1. What is graph theory?

Graph theory is a branch of mathematics that deals with the study of graphs, which are mathematical structures used to model relationships between objects. It involves analyzing the properties and characteristics of graphs, as well as developing algorithms and techniques for solving problems related to them.

2. How is graph theory used in real life?

Graph theory has a wide range of applications in various fields, including computer science, biology, social sciences, and transportation. It is used to model social networks, analyze computer networks and algorithms, design efficient transportation routes, and understand the structure and function of biological networks, among other things.

3. What are the basic components of a graph?

A graph consists of two fundamental components: vertices (also known as nodes) and edges. Vertices are the points or objects in a graph, while edges are the connections between them. In a directed graph, the edges have a specific direction, while in an undirected graph, the edges have no direction.

4. What are the different types of graphs?

There are several types of graphs, including directed and undirected graphs, weighted and unweighted graphs, and simple and multigraphs. Directed and undirected graphs differ in the directionality of their edges, while weighted and unweighted graphs have edges with different weights assigned to them. Simple graphs do not have multiple edges between the same pair of vertices, while multigraphs can have multiple edges between the same pair of vertices.

5. What are some common algorithms used in graph theory?

Some common algorithms used in graph theory include Dijkstra's algorithm, which finds the shortest path between two vertices in a weighted graph, and breadth-first search and depth-first search, which are used to traverse a graph and find all reachable vertices from a given starting point. Other important algorithms include Kruskal's algorithm for finding the minimum spanning tree of a graph and Ford-Fulkerson algorithm for finding the maximum flow in a network.

Similar threads

Replies
7
Views
2K
Replies
1
Views
1K
  • Programming and Computer Science
Replies
2
Views
1K
  • General Math
2
Replies
66
Views
4K
  • General Math
Replies
1
Views
949
  • Engineering and Comp Sci Homework Help
Replies
4
Views
967
  • Computing and Technology
Replies
2
Views
66
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • General Math
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
Back
Top