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
1914122257 1969999211 2082317855 2115831572
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 give a new proof showing that it is NP-hard to color a 3-colorable graph using just 4 colors. This result is already known , [S. Khanna, N. Linial, and S. Safra, Combinatorica, 20 (2000), pp. 393--415], but our proof is novel because it does not rely on the PCP theorem, while the known one does. This highlights a qualitative difference between the known hardness result for coloring 3-colorable graphs and the factor @math hardness for approximating the chromatic number of general graphs, as the latter result is known to imply (some form of) PCP theorem [M. Bellare, O. Goldreich, and M. Sudan, SIAM J. Comput., 27 (1998), pp. 805--915]. Another aspect in which our proof is novel is in its use of the PCP theorem to show that 4-coloring of 3-colorable graphs remains NP-hard even on bounded-degree graphs (this hardness result does not seem to follow from the earlier reduction of Khanna, Linial, and Safra). We point out that such graphs can always be colored using O(1) colors by a simple greedy algorithm, while the best known algorithm for coloring (general) 3-colorable graphs requires @math colors. Our proof technique also shows that there is an @math such that it is NP-hard to legally 4-color even a @math fraction of the edges of a 3-colorable graph. 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. For many random constraint satisfaction problems, by now there exist asymptotically tight estimates of the largest constraint density for which solutions exist. At the same time, for many of these problems, all known polynomial-time algorithms stop finding solutions at much smaller densities. For example, it is well-known that it is easy to color a random graph using twice as many colors as its chromatic number. Indeed, some of the simplest possible coloring algorithms achieve this goal. Given the simplicity of those algorithms, one would expect room for improvement. Yet, to date, no algorithm is known that uses (2 - epsiv)chi colors, in spite of efforts by numerous researchers over the years. In view of the remarkable resilience of this factor of 2 against every algorithm hurled at it, we find it natural to inquire into its origin. We do so by analyzing the evolution of the set of k-colorings of a random graph, viewed as a subset of 1,...,k n, as edges are added. We prove that the factor of 2 corresponds in a precise mathematical sense to a phase transition in the geometry of this set. Roughly speaking, we prove that the set of k-colorings looks like a giant ball for k ges 2chi, but like an error-correcting code for k les (2 - epsiv)chi. We also prove that an analogous phase transition occurs both in random k-SAT and in random hypergraph 2-coloring. And that for each of these three problems, the location of the transition corresponds to the point where all known polynomial-time algorithms fail. To prove our results we develop a general technique that allows us to establish rigorously much of the celebrated 1-step replica-symmetry-breaking hypothesis of statistical physics for random CSPs.