We study a certain relaxation of the classic vertex coloring problem, namely, a coloring of vertices of undirected, simple graphs, such that there are no monochromatic triangles. We give the first classification of the problem in terms of classic and parametrized algorithms. Several computational complexity results are also presented, which improve on the previous results found in the literature. We propose the new structural parameter for undirected, simple graphs -- the triangle-free chromatic number @math . We bound @math by other known structural parameters. We also present two classes of graphs with interesting coloring properties, that play pivotal role in proving useful observation about our problem. We give ask several conjectures questions throughout this paper to encourage new research in the area of graph coloring.
Some researchers have already considered coloring problems that are similar to our variation. The class of planar graphs has been of particular interest, for example, Angelini and Frati @cite_14 study planar graphs that admit an acyclic 3-coloring -- a proper coloring in which every 2-chromatic subgraph is acyclic. Algorithms for acyclic coloring can be used to solve approximate a triangle-free coloring, although we do not explore this possibility in this paper. Another result is of Kaiser and S krekovski @cite_1 , where they prove that every planar graph has a 2-coloring such that no cycle of length 3 or 4 is monochromatic. Thomassen @cite_2 , on the other hand, considers list-coloring of planar graphs without monochromatic triangles. Few hardness results for our problem are known -- Karpi 'nski @cite_20 showed that verifying whether a graph admits a 2-coloring without monochromatic cycles of fixed length is @math -complete. His proof was then simplified by Shitov @cite_12 , who also proposed and proved the hardness of an extension of our problem, where additional restriction is imposed on the coloring in the form of the set of polar edges -- edges that must not be monochromatic in the resulting coloring.
@cite_14 @cite_1 @cite_2 @cite_20 @cite_12
2089322292 1914122257 2082317855 2542720522 2588373402
In this paper we study the acyclic 3-colorability of some subclasses of planar graphs. First, we show that there exist infinite classes of cubic planar graphs that are not acyclically 3-colorable. Then, we show that every planar graph has a subdivision with one vertex per edge that is acyclically 3-colorable and provide a linear-time coloring algorithm. Finally, we characterize the series-parallel graphs for which every 3-coloring is acyclic and provide a linear-time recognition algorithm for such graphs. It is well known that every planar graph G is 2-colorable in such a way that no 3-cycle of G is monochromatic. In this paper, we prove that G has a 2-coloring such that no cycle of length 3 or 4 is monochromatic. The complete graph K5 does not admit such a coloring. On the other hand, we extend the result to K5-minor-free graphs. There are planar graphs with the property that each of their 2-colorings has a monochromatic cycle of length 3, 4, or 5. In this sense, our result is best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 25–38, 2004 We prove that, for every list-assignment of two colors to every vertex of any planar graph, there is a list-coloring such that there is no monochromatic triangle. This proves and extends a conjecture of B. Mohar and R. Skrekovski and a related conjecture of A. Kundgen and R. Ramamurthi. In this paper we study a problem of vertex two-coloring of an undirected graph such that there is no monochromatic cycle of the given length. We show that this problem is hard to solve. We give a proof by presenting a reduction from the variation of satisfiability (SAT) problem. We show the nice properties of coloring cliques with two colors which plays pivotal role in the reduction construction. For any integer k3, we consider the following decision problem. Given a simple graph, does there exist a partition of its vertices into two disjoint sets such that every simple k-cycle of G contains vertices in both of these sets? This problem is NP-hard because it admits a polynomial reduction from NAE 3-SAT. We construct a reduction that is polynomial both in the length of the instance and in k, which answers a recent question of Karpiski.