Coloring Graphs Using Two Colors While Avoiding Monochromatic Cycles

References

• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows: Theory, Algorithms, and Applications (1993) (Prentice-Hall, Upper Saddle River, NJ) Google Scholar
• Aifeng Y., Jinjiang Y. On the vertex arboricity of planar graphs of diameter two. Discrete Math. (1991) 307(19–20):2438–2447Crossref, Google Scholar
• Alekseev V. E., Farrugia A., Lozin V. V. New results on generalized graph coloring. Discrete Math. Theoret. Comput. Sci. (2004) 6(2):215–222Google Scholar
• Apollonio N., Franciosa P. G. A characterization of partial directed line graphs. Discrete Math. (2007) 307(21):2598–2614Crossref, Google Scholar
• Bartnicki T., Grytczuk J. A., Kierstead H. A. The game of arboricity. Discrete Math. (2008) 308(8):1388–1393Crossref, Google Scholar
• Bench-Capon T. J. M., Benferhat S., Giunchiglia E. Value-based argumentation frameworks. Proc. 9th Internat. Workshop Non-Monotonic Reasoning (2002) Toulouse, France:443–454Google Scholar
• Broersma H., Fomin F. V., Kratochvil J., Woeginger G. J. Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it diffcult. Algorithmica (2006) 44(4):343–361Crossref, Google Scholar
• Chen Z.-Z. Efficient algorithms for acyclic colorings of graphs. Theoret. Comput. Sci. (2000) 230(1–2):75–95Crossref, Google Scholar
• Cherchye L., De Rock B., Vermeulen F. The collective model of household consumption: A nonparametric characterization. Econometrica (2007) 75(2):553–574Crossref, Google Scholar
• Cherchye L., Rock B. D., Sabbe J., Vermeulen F. Nonparametric tests of collectively rational consumption behavior: An integer programming procedure. J. Econometrics (2008) 147(2):258–265Crossref, Google Scholar
• Cormen T. H., Leiserson C. E., Rivest R. L., Stein C.Introduction to Algorithms (2005) (MIT Press, Cambridge, MA) Google Scholar
• Deb R. Acyclic partitioning problem is NP-complete for k = 2. (2008a) . Private communication, April 28. Yale University, New Haven, CT.Google Scholar
• Deb R. An efficient nonparametric test of the collective household model. (2008b) . Working paper, Yale University, New Haven, CTCrossref, Google Scholar
• Farin G. Class A Bézier curves. Comput. Aided Geometric Design (2006) 23(7):573–581Crossref, Google Scholar
• Goddard W. Acyclic colorings of planar graphs. Discrete Math. (1991) 91(1):91–94Crossref, Google Scholar
• Hogg T. Refining the phase transition in combinatorial search. Artificial Intelligence (1985) 81(1–2):127–154Crossref, Google Scholar
• Karp R. M. The transitive closure of a random digraph. Random Structures Algorithms (1990) 1(1):73–93Crossref, Google Scholar
• Khanna S., Kumaran K. On wireless spectrum estimation and generalized graph coloring. Proc. INFOCOM'98 (1998) San Francisco(IEEE, Piscataway, NJ) 1273–1283Crossref, Google Scholar
• Lund C., Yannakakis M., Goos G., Hartmanis J. The approximation of maximum subgraph problems. Automata, Languages, Programming (ICALP 93) (1993) 700(Springer, Berlin) 40–51Lecture Notes in Computer ScienceCrossref, Google Scholar
• Monasson R., Zecchina R., Kirkpatrick S., Selman B., Troyansky L. Determining computational complexity from characteristic “phase transitions. Nature (1999) 400(6740):133–137Crossref, Google Scholar
• Raspaud A., Wang W. On the vertex-arboricity of planar graphs. Eur. J. Combinatorics (2008) 29(4):1064–1075Crossref, Google Scholar
• Roychoudhury A., Sur-Kolay S., Thiagarajan P. S. Efficient algorithms for vertex arboricity of planar graphs. Proc. 15th Conf. Foundations Software Tech. Theoret. Comput. Sci., Vol. 1026 (1995) (Springer, Berlin) 37–51Lecture Notes in Computer ScienceCrossref, Google Scholar
• Talla Nobibon F., Spieksma F. On the complexity of testing the collective axiom of revealed preference. Math. Soc. Sci. (2010) 60(2):123–136Crossref, Google Scholar
• Talla Nobibon F., Hurkens C., Leus R., Spieksma F., Chen B. Exact algorithms for coloring graphs while avoiding monochromatic cycles. Proc. 6th Internat. Conf. Algorithmic Aspects in Information and Management (AAIM 2010), Vol. 6124 (2010a) (Springer, Berlin) 229–242Lecture Notes in Computer ScienceCrossref, Google Scholar
• Talla Nobibon F., Cherchye L., Rock B. D., Sabbe J., Spieksma F. Heuristics for deciding collectively rational consumption behavior. Comput. Econom. (2010b) . ePub ahead of print June 10Google Scholar
• Tarjan R. Depth-first search and linear graph algorithms. SIAM J. Comput. (1972) 1(2):146–160Crossref, Google Scholar
• Thomassen C. 2-list-coloring planar graphs without monochromatic triangles. J. Combin. Theory (2008) 98(6):1337–1348Crossref, Google Scholar
• Thorsteinsson E. S., Walsh T. Branch-and-check: A hybrid framework integrating mixed integer programming and constraint logic programming. Principles Practice Constraint Programming (CP 2001), Vol. 2239. (2001) (Springer, Berlin) 16–30Lecture Notes in Computer ScienceCrossref, Google Scholar
• Varian H. R., Szenberg M., Ramrattan L., Gottesman A. A. Revealed preference. Samuelsonian Economics and the Twenty-First Century (2006) (Oxford University press, Oxford, UK) 99–115Crossref, Google Scholar
• Wu Y., Yuan J., Zhao Y. Partition a graph into two induced forests. J. Math. Stud. (1996) 29(1):1–6Google Scholar