A survey of graph coloring - its types, methods and applications

DOI10.2478/v10209-011-0012-yzbMath1360.05057OpenAlexW2076967887MaRDI QIDQ2978431

Krzysztof Tanaś, Piotr Formanowicz

Publication date: 25 April 2017

Published in: Foundations of Computing and Decision Sciences (Search for Journal in Brave)

Full work available at URL: https://www.degruyter.com/view/j/fcds.2012.37.issue-3/v10209-011-0012-y/v10209-011-0012-y.xml?format=INT

zbMATH Keywords

complexityalgorithmsgraph coloringedge coloringvertex coloring

Mathematics Subject Classification ID

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

Related Items

An efficient parallel block coordinate descent algorithm for large-scale precision matrix estimation using graphics processing units, Computational complexity of distance edge labeling, Solving graph coloring problems with the Douglas-Rachford algorithm, A systematic study on meta-heuristic approaches for solving the graph coloring problem, An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm, COMPUTATION OF b-CHROMATIC TOPOLOGICAL INDICES OF SOME GRAPHS AND ITS DERIVED GRAPHS, Optimal secret share distribution in degree splitting communication networks, A Lower Bound of the cd-Chromatic Number and Its Complexity, Unnamed Item, Total coloring conjecture for certain classes of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Acyclic and star colorings of cographs
• Acyclic colorings of subcubic graphs
• Precoloring extension. I: Interval graphs
• Some simplified NP-complete graph problems
• A bound on the total chromatic number
• Fulkerson's conjecture and circuit covers
• Algorithmic aspects of acyclic edge colorings
• Acyclic edge colorings of graphs
• Acyclic edge-colouring of planar graphs. Extended abstract
• The Fan–Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks
• Star coloring of graphs
• Star chromatic number
• The NP-Completeness of Edge-Coloring
• Acyclic coloring of graphs
• Every planar map is four colorable
• New methods to color the vertices of a graph
• Tree search algorithms for the dominating vertex set problem
• Equitable Coloring
• Blocking and anti-blocking pairs of polyhedra
• 25 pretty graph colouring problems
• Circular chromatic number: A survey