Greedy algorithms for triangle free coloring

zbMATH Open1262.05063MaRDI QIDQ1927697FDOQ1927697

Authors: Sándor Szabó, Bogdán Zaválnij 

Publication date: 2 January 2013

Published in: AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Recommendations

• Colouring vertices of triangle-free graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Fast 3-coloring triangle-free planar graphs
• Coloring the Maximal Cliques of Graphs
• A class of three-colorable triangle-free graphs

zbMATH Keywords

maximum cliquecliqueindependent setgreedy coloringvertex coloringclique search algorithm\(s\)-clique free coloring\(s\)-clique free setsatisfiability solver

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Cited In (6)

• Numerical experiments with LP formulations of the maximum clique problem
• Reducing graph coloring to clique search
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Decomposing clique search problems into smaller instances based on node and edge colorings

This page was built for publication: Greedy algorithms for triangle free coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1927697)