An expected polynomial time algorithm for coloring 2-colorable 3-graphs

DOI10.1016/j.endm.2009.07.077zbMath1273.05223OpenAlexW1580012115MaRDI QIDQ2851504

Yury Person, Mathias Schacht

Publication date: 10 October 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-00990504/file/1357-6016-1-PB.pdf

zbMATH Keywords

hypergraphscoloringaverage case analysis

Mathematics Subject Classification ID

Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Degree, Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs, An expected polynomial time algorithm for coloring 2-colorable 3-graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• The hardness of 3-uniform hypergraph coloring
• The Turán number of the Fano plane
• Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
• An expected polynomial time algorithm for coloring 2-colorable 3-graphs
• The solution of some random NP-hard problems in polynomial expected time
• Hardness of Approximate Hypergraph Coloring
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Almost all k-colorable graphs are easy to color
• Coloring Clique-free Graphs in Linear Expected Time
• An Algorithmic Regularity Lemma for Hypergraphs
• Coloring bipartite hypergraphs
• Triple Systems Not Containing a Fano Configuration