Books in Combinatorial optimization

$\begingroup$

I wrote Combinatorial optimization in the title , but I am not sure if this is what I am looking for. Recently, I was getting more interested in Koing's theorem, Hall marriage theorem . I am interested to see similar theorems (I know similar is subjective). I guess what I am looking for is combinatorial optimization.

I am wouldn't be interested about the algorithmic side of Combinatorial optimization. I just want to get exposed to some nice theorems of the subject like the ones I mentioned at the beginning. I need suggestions for a suitable book.

Note: I only took an undergrad course in graph theory. I don't mind if the book is a graduate level book as long as it does not assume a pre knowledge of the subject.

Thank you

Edit: I would also be interested about coloring problems of graphs and the chromatic number. I think I am interested in problems where one is looking for a maximum or a minimum. But I am not interested in making algorithms to achieve a maximum or a minimum.

$\endgroup$ 6

2 Answers

$\begingroup$

[Comments turned into an answer:]

I believe combinatorial optimization is the natural way to go from Hall and König. Extremal graph theory mostly restricts itself to graphs (rather than decorated graphs, matroids, jump systems and all the other fancy objects combinatorial optimization is occupied with), about which it asks deeper questions. It is you who will ultimately have to decide what is more natural for you.

Lex Schrijver has both a 3-volume book on combinatorial optimization and a set of lecture notes ( ; these contain some extremal graph theory, too, in their Chapter 7). I don't think you can easily split away the algorithmic side from the slick side: the algorithms are as central to this subject as are proofs, and often are more or less the proofs. (What you can ignore, if you want to, is the running time estimates; but they aren't usually the hard part...) You'll probably like matroids if you want to see things similar to Hall and König.

$\endgroup$ $\begingroup$

Applied Combinatorics. Alan Tucker. It has some graph theory with the most prominent theorems and proofs, but also other techniques. Link to 6th ed:

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy