Coloring Graphs Using Two Colors While Avoiding Monochromatic Cycles

DOI10.1287/ijoc.1110.0466zbMath1461.05096MaRDI QIDQ2815462

Roel Leus, Frits C. R. Spieksma, Fabrice Talla Nobibon, Cor A. J. Hurkens

Publication date: 29 June 2016

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://orbi.ulg.ac.be/handle/2268/97782

zbMATH Keywords

bipartite graph; phase transition; directed graph; NP-complete; undirected graph; acyclic graph

Mathematics Subject Classification ID

90C10: Integer programming

05C38: Paths and cycles

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

Related Items

Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete, Reformulated acyclic partitioning for rail-rail containers transshipment, Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT, Revealed Preference Tests of Collectively Rational Consumption Behavior: Formulations and Algorithms

Cites Work

• Nonparametric tests of collectively rational consumption behavior: an integer programming procedure
• Heuristics for deciding collectively rational consumption behavior
• 2-list-coloring planar graphs without monochromatic triangles
• Efficient algorithms for acyclic colorings of graphs
• On the vertex arboricity of planar graphs of diameter two
• On the vertex-arboricity of planar graphs
• A characterization of partial directed line graphs
• The game of arboricity
• Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult
• Class A Bézier curves
• On the complexity of testing the collective axiom of revealed preference
• Efficient algorithms for vertex arboricity of planar graphs
• The transitive closure of a random digraph
• Exact Algorithms for Coloring Graphs While Avoiding Monochromatic Cycles
• The Collective Model of Household Consumption: A Nonparametric Characterization
• Depth-First Search and Linear Graph Algorithms
• Acyclic colorings of planar graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item