From: rusin@math.niu.edu (Dave Rusin) Newsgroups: sci.math.research Subject: Graph-coloring query Date: 14 Jun 1997 17:49:39 GMT A graph can be 2-colored iff if contains no cycle of odd length. Note that a cycle is a subgraph homeomorphic to the complete graph K3 on three vertices. A necessary condition for 4-coloring is that the graph contain no K5; a sufficient condition is that it contain no subgraph homeomorphic to K5 nor any homeomorphic to the 3-utilities-3-houses graph. Is there a characterization of graphs which are 3-colorable? Again, it is necessary that the graph contain no K4, but this is not sufficient. Starter references would be appreciated. dave ============================================================================== Date: Sun, 15 Jun 1997 15:42:33 -0400 (EDT) From: [Permission pending] To: rusin@math.niu.edu Subject: Re: Graph-coloring query Newsgroups: sci.math.research >A necessary condition for 4-coloring is that the graph contain no K5; >a sufficient condition is that it contain no subgraph homeomorphic to >K5 nor any homeomorphic to the 3-utilities-3-houses graph. i.e., K3,3 (to recall notation) >Is there a characterization of graphs which are 3-colorable? Again, >it is necessary that the graph contain no K4, nor any K2,3 (itself: I don't know about homeomorphs) >but this is not sufficient. Is this? I dunno. But the pattern's cute, isn't it. ============================================================================== From: Gareth McCaughan Newsgroups: sci.math.research Subject: Re: Graph-coloring query Date: 15 Jun 1997 16:57:41 +0100 rusin@math.niu.edu (Dave Rusin) writes: > A necessary condition for 4-coloring is that the graph contain no K5; > a sufficient condition is that it contain no subgraph homeomorphic to > K5 nor any homeomorphic to the 3-utilities-3-houses graph. :-) > Is there a characterization of graphs which are 3-colorable? Again, > it is necessary that the graph contain no K4, but this is not sufficient. "The Four-Color Problem" (Saaty & Kainen, publ. Dover) mentions the following: Theorem 2-5 A cubic map is three-colorable if and only if each region is bounded by an even number of sides. (note that that says "map", not "graph") Theorem 2-6 A triangular map M can be three-colored if and only if U(M) /= K_4. (U(M) is the "underlying graph" of the map: e.g., the underlying graph of a triangular region is a cycle with 3 vertices.) Theorem 2-7 If G is a planar graph which contains no cycle of length 3, then G can be three-colored. (They describe this as "one of the few general results on three-coloring planar graphs"; the reference they give is to H. Groetzsch, "Ein Dreifarbensatz fur Dreikreisfrei Netze auf der Kugel", Wiss. Z. Martin- -Luther Univ. Halle-Wittenburg Math. Naturwiss. Reihe, vol 8, 1958.) -- Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics, gjm11@dpmms.cam.ac.uk Cambridge University, England. ============================================================================== From: yerman@vespucci.iquest.com (Niall Graham) Newsgroups: sci.math.research Subject: Re: Graph-coloring query Date: 16 Jun 1997 22:12:06 -0500 >Is there a characterization of graphs which are 3-colorable? No. The question "Is G 3-colorable?" is NP-complete. Unless P=NP, any characterization of 3-colorable graphs (or more importantly non-3-colorable graphs) would be such that it would require super-polynomial time to check, and hence, would probably be rather complicated. In general there is an interesting interplay between NP-complete problems and (the absence of) corresponding characterization theorems. For example, there is no characterization of hamiltonian graphs. The intuition is that any "reasonable" characterization theorem would prove P=NP. Niall Graham University of Alabama, Huntsville ============================================================================== From: [Permission pending] Date: Tue, 17 Jun 1997 12:31:45 -0400 (EDT) To: rusin@math.niu.edu Subject: Re: Graph-coloring query Newsgroups: sci.math.research Every 3-chromatic graph can be contracted to K_3. This is the n=3 case of Hadwiger's conjecture, first proved by Dirac. I don't think there is any nice *characterization* of 3-colorability, though. [Permission pending] ============================================================================== Date: Tue, 17 Jun 1997 11:40:14 -0500 (CDT) From: [Permission pending] To: rusin@math.niu.edu Subject: Re: Graph-coloring query see Garey and Johnston 's book. I'm posting from home, and it is in my office. Good luck, [P.p.] ============================================================================== Date: Thu, 19 Jun 1997 10:24:24 -0500 To: rusin@math.niu.edu From: [Permission pending] Subject: Belatedly on graph coloring question Hello Dave, Sorry for the delay in replying. Your email was one of a large backlog which I got during several days absence recently, and I didn't get around to it earlier this week because summer teaching has started and I've been scrambling to get out syllabi, set up class records, prepare assignments, etc. I'm off to DeKalb later today, and no doubt will get to talk with you tomorrow! A short answer to one of your key questions: there is effectively no characterization of 3-chromatic ordinary graphs. With the exception of odd cycles and complete graphs, max degree is an upper bound on chromatic number of a connected graph (Brooks, 1941), but there are graphs of arbitrarily large girth with arbitrarily large chromatic number (existentially by Erd=F6s, 1961; constructively by Lov=E1sz, 1968). In haste, [Permission pending] >Dear [deletia -- djr] I'm not well >versed in matters of graph colorings and so on, so I've been trying to >read background material and think about related topics. This led me to a >question on one of these topics; Richard Blecksmith suggested I ask >you about it. > >Manning's thesis concerns minimal 4-uniform hypergraphs with chromatic >number greater than 2. He is ultimately interested in ones which are >"minimal" in the sense of having the smallest number of quads, but I >think it's interesting to speculate more generally about ones which >are "minimal" in the sense of inclusion. > >Indeed, he includes a chapter on 3-uniform hypergraphs, in which he >catalogues a number of small designs which are not 2-colorable. As I >read through that chapter I wonder whether it would be reasonable to >ask for a characterization of such non-2-colorable 3-uniform hypergraphs. > >To warm up to this, I dropped back further to 2-uniform hypergraphs >(i.e. ordinary graphs). THere, 2-coloring is simple to decide: a >graph is 2-colorable iff it contains no cycle of odd length. One can >think of it this way: the very smallest graph which is not 2-colorable is >the complete graph K3 on 3 vertices; all the other cycles are obtained >by inserting a chain * - * - * in a shorter cycle, since in a >2-coloring, the ends of this chain must have the same color. Note that >2-colorability is then characterized by a topological invariant (embedded >circles) and a numerical one (odd length). > >Of course, 4-coloring is classic and difficult, but we have a sufficient >condition which is purely topological (no embedded graph topolgically >equivalent to K5 or the 3-utilities-3-houses graph). I suppose there >are some numerical or parity conditions which are also necessary. >Ideally some combination of topological and numerical conditions would >be necessary and sufficient. > >I tried the intermediate case of 3-colorings (of ordinary graphs). >Is it possible to characterize the minimal graphs (in the sense of inclusio= n) >which admit no 3-coloring? Certainly K4 is such a graph. As with >the 2-coloring of graphs, it is possible to make many more graphs >which admit no 3-coloring: simply insert copies of a "split square" > - * ---- * > | \ | > | \ | > | \ | > | \ | > * ---- * - >whose outer corners will have the same color in any 3-coloring. >The same is true of this figure (a "cut gem") > * > _/| |\_ > _/ / \ \_ > _/ | | \_ > / / \ \ > - * --- * * --- * - > \ \ / / > \ \ / / > \ * / > \ | / > \ | / > \ | / > \ | / > * >which contains neither a K4 nor a split square; I'm guessing that if >I keep playing with it I can construct such a figure which doesn't even >contain triangles. Clearly, by inserting these figures into a K4 we can >construct many minimal non-3-colorable graphs. Thus the situation is >clearly murky (hm, that doesn't read very well, does it?). > >So now I am led to ask what is known about this circle of ideas. > - Is there a characterization of minimal graphs with chromatic > number greater than 3? > - Is there a characterization of minimal 3-uniform hypergraphs > with chromatic number greater than 2? >(It's the latter question which is more relevant for Manning's thesis >but the former seems more classical.) I would appreciate any pointers >to the literature. > [deletia -- djr]