Hi, I'm a high school student and writing a paper about graph coloring. Can you tell me something about some interesting problems in graph theory connected with graph coloring? Such as full triangle coloring or 2COL problem? i will be pleased. :)
Sorry for my bad english, John
If you care to go beyond plane-graph coloring, I can recommend the readable note by Michael Albertson and Joan Hutchinson, "Hadwiger's conjecture and six chromatic toroidal graphs," Graph Theory and Related Topics (PDF link), and the later, equally readable paper by Karen Collins and Joan Hutchinson, "Four-Coloring Six-Regular Graphs On The Torus" Discrete Mathematics, Volume 273, Issues 1–3, 6 December 2003, Pages 261–274 (Journal link; PDF link).
I suppose that by now OP is out of high school and maybe even in graduate school, but perhaps he, or someone else, will still find the following interesting.
Let $\Gamma(G,k)$ be the chromatic polynomial of the graph $G$, which gives you the number of ways to color the vertices of $G$ when $k$ colors are available, in such a way that adjacent vertices get different colors. If $G$ is chordal (that is, if every $n$-cycle in $G$ for $n\ge4$ has a chord in $G$), then it's easy to work out $\Gamma(G,k)$ by just "following your nose". If $G$ is not chordal, then there are two formulas that are commonly taught as iterative ways to find $\Gamma(G,k)$: $$\Gamma(G,k)=\Gamma(G-e,k)-\Gamma(G/e,k)\tag1$$ where $G-e$ means delete the edge $e$ from $G$, and $G/e$ means contract the edge $e$ (that is, identify its endpoints), and $$\Gamma(G,k)=\Gamma(G+e,k)+\Gamma(G/e,k)\tag2$$ where $G+e$ means add the edge $e$ to $G$. Mathematically, these are just two different ways to write the same formula, but in practice there are examples where one of them gets you to the answer faster than the other. The problem I propose is finding graphs where (2) gets you there faster than (1). I've read that (1) is better for sparse graphs, and (2) is better for dense graphs, but I'm not wholly convinced.
The examples I've found are mostly based on bipartite graphs. E.g., if $G=K_{2,3}$, then one application of (2) does the trick (letting $e$ be the edge joining the two vertices in the 2-part of $K_{2,3}$), whereas two applications of (1) are needed. More generally, if you take $K_{m,n}$ with $m\ge2$ and $n\ge3$, and optionally add a few edges joining a few pairs of vertices that aren't already joined, you can get more examples where (2) beats (1).
The only other examples I've found are based on the graph $G$ that consists of the 8-cycle $ABCDEFGH$ together with the 4-cycle $ACEG$. You have to apply (1) three times to get $\Gamma(G,k)$, but a single application of (2) (with $e=AE$ or $e=CG$) gets you the answer.
So the question is whether there are examples unrelated to the ones above (preferably examples small enough to be done by hand, by undergraduates) where (2) beats (1).
