Computational aspects of greedy partitioning of graphs

DOI10.1007/s10878-017-0185-2zbMath1385.68016OpenAlexW2767308712WikidataQ59610242 ScholiaQ59610242MaRDI QIDQ1702844

Piotr Borowiecki

Publication date: 1 March 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-017-0185-2

zbMATH Keywords

computational complexitygreedy algorithmgraph coloringgraph partitioningGrundy numberminimal graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Dynamic \(F\)-free coloring of graphs ⋮ Graph classes generated by Mycielskians ⋮ Generalized Coloring of Permutations

Uses Software

• CriticalPfreeGraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-fit coloring of bounded tolerance graphs
• Results on the Grundy chromatic number of graphs
• A note on first-fit coloring of interval graphs
• First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs
• Some perfect coloring properties of graphs
• Some simplified NP-complete graph problems
• On-line 3-chromatic graphs. II: Critical graphs
• On the Grundy number of graphs with few \(P_4\)'s
• The complexity of generalized graph colorings
• New potential functions for greedy independence and coloring
• Constructions of \(k\)-critical \(P_5\)-free graphs
• An interpolation theorem for partitions which are complete with respect to hereditary properties
• New upper bounds for the chromatic number of a graph
• Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
• New bounds for the chromatic number of graphs
• On the computational complexity of (O,P)-partition problems
• Graph Classes: A Survey
• Obstructions for three-coloring graphs with one forbidden induced subgraph
• On Computational Aspects of Greedy Partitioning of Graphs
• On-line P-coloring of graphs

This page was built for publication: Computational aspects of greedy partitioning of graphs