On Computational Aspects of Greedy Partitioning of Graphs

DOI10.1007/978-3-319-59605-1_4zbMath1489.68183OpenAlexW2619471257WikidataQ62043601 ScholiaQ62043601MaRDI QIDQ4632201

Piotr Borowiecki

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: http://link.springer.com/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) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) 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)

Related Items (1)

Computational aspects of greedy partitioning of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• An interpolation theorem for partitions which are complete with respect to hereditary properties
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• New bounds for the chromatic number of graphs

This page was built for publication: On Computational Aspects of Greedy Partitioning of Graphs