4 ms·
For those not familiar: K-Coloring is the property that a graph can be colored with k colors such that no two neighboring nodes get the same color. The K-Color
by emil-lp 2mo ago
For those not familiar:
K-Coloring is the property that a graph can be colored with k colors such that no two neighboring nodes get the same color. The K-Coloring problem is a decision problem, ie a yes/no question.
The chromatic number of a graph is the lowest k for which it has a k-coloring.
Clearly, if you have an algorithm for one, you have an algorithm for the other.
The question was: is it faster to compute k-coloring than to compute its lowest (actual) k, ie its chromatic number.
Forests, trees, and bipartite graphs are 2-colorable. Planar graphs are 4-colorable. It is NP-complete to check if the chromatic number of a planar graph is 3.
There's a very interesting open problem, Hadwiger's conjecture that essentially says that the chromatic number is the clique (minor) number (whatever that means).
- aleph_minus_one 2mo ago> Forests, trees, and bipartite graphs are 2-colorable. More precise: a graph is bipartite if and only if it is 2-colorable (this can actually be used as a definition). Since forests are bipartite, and trees are forests, the other two statements follow.
- emil-lp 2mo agoPrecisely! The reason I mentioned trees and forests are because they are probably more familiar. The Bipartite graph class is also a bit silly in this case, since it's by definition the 2-colorable graphs: bipartite, or 2-partite are the graphs that can be partitioned into 2 (color)classes such that no edge is internally in a class. More generally, the k-colorable graphs are exactly the k-partite graphs.
- aleph_minus_one 2mo ago> The Bipartite graph class is also a bit silly in this case, since it's by definition the 2-colorable graphs Be a little bit careful here: another common textbook definitions of bipartite graphs are: - a graph is bipartite iff it has no odd circle. - (for people who are into algebraic/spectral graph theory :-) ) a graph is bipartite iff its spectrum is symmetric. I personally like the latter two definitions because the "normal" definition of a bipartite graph suggests that 1-colorable, 2-colorable, 3-colorable, 4-colorable, ... graphs are conceptually very "similar" (k-colorable with different values for k). But we now that it is very easy (i.e. there exists a polynomial-time algorithm) to decide if a graph is 1- or 2-colorable, but from k=3 on, it is NP-complete to decide whether a given graph is k-colorable. Using one of these alternative definitions (and then showing "a graph is bipartite iff it is 2-colorable" as a lemma/theorem) makes it very clear that from a complexity point being 1- or 2-colorable is (assuming P != NP) something very different from being k-colorable for k >= 3.
- LegionMammal978 2mo agoOne curiosity that in the case of infinite graphs, "no odd cycles" doesn't imply "2-colorable" without the axiom of choice for families of 2-element sets [0]. It's somewhat similar to how in the definition of a well-founded relation, "no infinite descending chains" doesn't imply "every nonempty subset has a minimal element" without dependent choice. (One of my recent projects has been trying to prove the existence of a 2-colorable subgraph for a certain class of infinite graphs in ZF, which has led me surprisingly deep into choice principles and models refuting them.) [0] https://mathoverflow.net/a/453944 https://mathoverflow.net/a/453944
- aleph_minus_one 2mo agoThis is a really cool fact. :-)
- deleted 2mo ago[deleted]
- fithisux 2mo agoThank you.