Coloring Graphs Using Two Colors While Avoiding Monochromatic Cycles

DOI10.1287/ijoc.1110.0466zbMath1461.05096OpenAlexW2145323293MaRDI 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 graphphase transitiondirected graphNP-completeundirected graphacyclic graph

Mathematics Subject Classification ID

Integer programming (90C10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (4)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Coloring Graphs Using Two Colors While Avoiding Monochromatic Cycles