Let $G$ be a graph in which any two odd cycles have a common vertex. It is easy to see that $\chi(G)\leq 5$ (choose minimal odd cycle $C$, use two colors for $G\setminus C$ and three colors for $C$). And this is sharp as $K_5$ shows. May we improve this bound to $\chi(G)\leq 4$ assuming additionally that $G$ does not contain $K_5$? Or to $\chi(G)\leq 3$ assuming that $G$ does not contain $K_4$? I can not prove even $\chi(G)\leq 4$ for $G$ without $K_3$.
$\begingroup$
$\endgroup$
5
asked Oct 16, 2015 at 7:39
-
$\begingroup$ The cycles need not be induced, right? $\endgroup$– joroCommented Oct 16, 2015 at 8:00
-
$\begingroup$ It does not matter, since any any odd cycle contains induced odd cycle. $\endgroup$– Fedor PetrovCommented Oct 16, 2015 at 8:05
-
$\begingroup$ If there are at most two odd cycles, and they have a common a vertex, then our graph is (bipartite plus a vertex), hence 3-colorable. $\endgroup$– Fedor PetrovCommented Oct 16, 2015 at 9:16
-
2$\begingroup$ $G$ may be 4-chromatic even if it does not contain $K_3$. An example is provided by the Mycielski graph of $C_5$. To see that it does not contain two disjoint odd cycles, notice that each odd cycle either contains the apex and an edge of $C_5$, or contains at least one of any two neighbors in $C_5$. $\endgroup$– Ilya BogdanovCommented Oct 16, 2015 at 9:18
-
2$\begingroup$ More generally, any non-bipartite quadrangulation of the projective plane is an example (any two odd cycles intersect, since they correspond to non-contractible curves on the surface), and it is known that they are 4-chromatic (D.A. Youngs, 4-chromatic projective graphs, J. Graph Theory 21 (1996), 219-227). The Mycielski graph is a particular case. $\endgroup$– Louis EsperetCommented Oct 16, 2015 at 12:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
The claim on graphs without $K_5$ is a particular case of the (still open in general) Erdos--Lovasz Tihany conjecture. (Tihany is not a surname, but the name of a peninsula on Balaton lake in Hungary.)
This particular case has been proved in W.G. Brown and H.A. Jung, On odd circuits in chromatic graphs, Acta Math. Acad. Sci. Hungarica, V. 20(1), pp. 129-134. In fact, this paper contains more general results.
As I already mentioned in the comments, this bound cannot be lowered to 3 even if the graph contains no $K_3$. An example is provided by the Mycielski graph of $C_5$. To see that it does not contain two disjoint odd cycles, notice that each odd cycle either contains the apex and an edge of $C_5$, or contains at least one of any two neighbors in $C_5$.
