New potential functions for greedy independence and coloring
From MaRDI portal
Publication:2255044
DOI10.1016/j.dam.2013.12.011zbMath1306.05175OpenAlexW2018967511WikidataQ62043609 ScholiaQ62043609MaRDI QIDQ2255044
Piotr Borowiecki, Dieter Rautenbach
Publication date: 6 February 2015
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2013.12.011
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)
Related Items (5)
A lower bound on the independence number of a graph in terms of degrees and local clique sizes ⋮ Dynamic \(F\)-free coloring of graphs ⋮ Computational aspects of greedy partitioning of graphs ⋮ On Computational Aspects of Greedy Partitioning of Graphs ⋮ On zero-error codes produced by greedy algorithms
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Independence in connected graphs
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- The struction of a graph: Application to CN-free graphs
- Some perfect coloring properties of graphs
- Lower bounds on the stability number of graphs computed in terms of degrees
- Small transversals in hypergraphs
- On an upper bound of the graph's chromatic number, depending on the graph's degree and density
- On the chromatic index of almost all graphs
- Zero knowledge and the chromatic number
- A probabilistic lower bound on the independence number of graphs
- On-line 3-chromatic graphs. II: Critical graphs
- Polynomial approximation and graph-coloring
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Lower bounds on the independence number in terms of the degrees
- Forbidden subgraphs implying the MIN-algorithm gives a maximum independent set
- Polynomially solvable cases for the maximum stable set problem
- NP-hard graph problems and boundary classes of graphs
- New upper bounds for the chromatic number of a graph
- On the Grundy Number of a Graph
- GreedyMAX-type Algorithms for the Maximum Independent Set Problem
- On the Maximum Independent Set Problem in Subclasses of Planar Graphs
- Graphs with chromatic numbers strictly less than their colouring numbers
- New bounds for the chromatic number of graphs
- Set Partitioning via Inclusion-Exclusion
- Measure and conquer
- New approximation algorithms for graph coloring
- The potential of greed for independence
- On the stability number of AH‐free graphs
- Graph Colorings
- An inequality for the chromatic number of a graph
- The smallest triangle-free 4-chromatic 4-regular graph
- On the independence number of a graph in terms of order and size
This page was built for publication: New potential functions for greedy independence and coloring
