Goldberg–Seymour conjecture
In graph theory the Goldberg–Seymour conjecture states that where is the edge chromatic number of G and Note this above quantity is twice the arboricity of G. It is sometimes called the density of G.
Symmetric hypergraph theorem
The Symmetric hypergraph theorem is a theorem in combinatorics that puts an upper bound on the chromatic number of a graph (or hypergraph in general). The original reference for this paper is unknown
Gallai–Hasse–Roy–Vitaver theorem
In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that the minim
Chromatic polynomial
The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was origina
Oriented coloring
In graph theory, oriented graph coloring is a special type of graph coloring. Namely, it isan assignment of colors to vertices of an oriented graph that
* is proper: no two adjacent vertices get the
Interval chromatic number of an ordered graph
In mathematics, the interval chromatic number X<(H) of an ordered graph H is the minimum number of intervals the (linearly ordered) vertex set of H can be partitioned into so that no two vertices belo
Interval edge coloring
In graph theory, interval edge coloring is a type of edge coloring in which edges are labeled by the integers in some interval, every integer in the interval is used by at least one edge, and at each
Brooks' theorem
In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most
Heawood conjecture
In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. For surfaces of genus
Incidence coloring
In graph theory, the act of coloring generally implies the assignment of labels to vertices, edges or faces in a graph. The incidence coloring is a special graph labeling where each incidence of an ed
Complete coloring
In graph theory, a complete coloring is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense tha
Snark (graph theory)
In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, sna
Fractional coloring
Fractional coloring is a topic in a young branch of graph theory known as . It is a generalization of ordinary graph coloring. In a traditional graph coloring, each vertex in a graph is assigned some
List edge-coloring
In mathematics, list edge-coloring is a type of graph coloring that combines list coloring and edge coloring.An instance of a list edge-coloring problem consists of a graph together with a list of all
Hadwiger–Nelson problem
In geometric graph theory, the Hadwiger–Nelson problem, named after Hugo Hadwiger and Edward Nelson, asks for the minimum number of colors required to color the plane such that no two points at distan
Albertson conjecture
In combinatorial mathematics, the Albertson conjecture is an unproven relationship between the crossing number and the chromatic number of a graph. It is named after Michael O. Albertson, a professor
Monochromatic triangle
In graph theory and theoretical computer science, the monochromatic triangle problem is an algorithmic problem on graphs,in which the goal is to partition the edges of a given graph into two triangle-
Hajós construction
In graph theory, a branch of mathematics, the Hajós construction is an operation on graphs named after György Hajós that may be used to construct any critical graph or any graph whose chromatic number
Precoloring extension
In graph theory, precoloring extension is the problem of extending a graph coloring of a subset of the vertices of a graph, with a given set of colors, to a coloring of the whole graph that does not a
Grundy number
In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the g
Path coloring
In graph theory, path coloring usually refers to one of two problems:
* The problem of coloring a (multi)set of paths in graph , in such a way that any two paths of which share an edge in receive dif
Exact coloring
In graph theory, an exact coloring is a (proper) vertex coloring in which every pair of colors appears on exactly one pair of adjacent vertices.That is, it is a partition of the vertices of the graph
Kempe chain
In mathematics, a Kempe chain is a device used mainly in the study of the four colour theorem. Intuitively, it is a connected chain of points on a graph with alternating colors.
Defective coloring
In graph theory, a mathematical discipline, coloring refers to an assignment of colours or labels to vertices, edges and faces of a graph. Defective coloring is a variant of proper vertex coloring. In
L(h, k)-coloring
In graph theory, a L(h, k)-labelling, L(h, k)-coloring or sometimes L(p, q)-coloring is a (proper) vertex coloring in which every pair of adjacent vertices has color numbers that differ by at least h,
Radio coloring
In graph theory, a branch of mathematics, a radio coloring of an undirected graph is a form of graph coloring in which one assigns positive integer labels to the graphssuch that the labels of adjacent
Well-colored graph
In graph theory, a subfield of mathematics, a well-colored graph is an undirected graph for which greedy coloring uses the same number of colors regardless of the order in which colors are chosen for
DSatur
DSatur is a graph colouring algorithm put forward by Daniel Brélaz in 1979. Similarly to the greedy colouring algorithm, DSatur colours the vertices of a graph one after another, adding a previously u
Hedetniemi's conjecture
In graph theory, Hedetniemi's conjecture, formulated by in 1966, concerns the connection between graph coloring and the tensor product of graphs. This conjecture states that Here denotes the chromatic
Heawood number
In mathematics, the Heawood number of a surface is an upper bound for the number of colors that suffice to color any graph embedded in the surface. In 1890 Heawood proved for all surfaces except the s
Uniquely colorable graph
In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors. Equivalently, there is only one way to partition its
Tricolorability
In the mathematical field of knot theory, the tricolorability of a knot is the ability of a knot to be colored with three colors subject to certain rules. Tricolorability is an isotopy invariant, and
Circular coloring
In graph theory, circular coloring is a kind of coloring that may be viewed as a refinement of the usual graph coloring. The circular chromatic number of a graph , denoted can be given by any of the f
Edge coloring
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edg
Rainbow coloring
In graph theory, a path in an edge-colored graph is said to be rainbow if no color repeats on it. A graph is said to be rainbow-connected (or rainbow colored) if there is a rainbow path between each p
The Mathematical Coloring Book
The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators is a book on graph coloring, Ramsey theory, and the history of development of these areas, concentrating i
Perfectly orderable graph
In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the g
Shift graph
In graph theory, the shift graph Gn,k for is the graph whose vertices correspond to the ordered -tuples with and where two vertices are adjacent if and only if or for all . Shift graphs are triangle-f
Five color theorem
The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the countries of the world, the regions may be colored using no more than fiv
Vizing's theorem
In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree Δ of the graph.At least Δ co
Dinitz conjecture
In combinatorics, the Dinitz theorem (formerly known as Dinitz conjecture) is a statement about the extension of arrays to partial Latin squares, proposed in 1979 by Jeff Dinitz, and proved in 1994 by
Erdős–Faber–Lovász conjecture
In graph theory, the Erdős–Faber–Lovász conjecture is a problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972. It says: If k complete graphs,
Χ-bounded
In graph theory, a -bounded family of graphs is one for which there is some function such that, for every integer the graphs in with (clique number) can be colored with at most colors. This concept an
Rainbow matching
In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.
Road coloring theorem
In graph theory the road coloring theorem, known previously as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach
Subcoloring
In graph theory, a subcoloring is an assignment of colors to a graph's vertices such that each color class induces a vertex disjoint union of cliques. That is, each color class should form a cluster g
List coloring
In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent pa
Tree-depth
In graph theory, the tree-depth of a connected undirected graph is a numerical invariant of , the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gon
Conflict-free coloring
Conflict-free coloring is a generalization of the notion of graph coloring to hypergraphs.
Adjacent-vertex-distinguishing-total coloring
In graph theory, a total coloring is a coloring on the vertices and edges of a graph such that: (1). no adjacent vertices have the same color; (2). no adjacent edges have the same color; and (3). no e
Weak coloring
In graph theory, a weak coloring is a special case of a graph labeling. A weak k-coloring of a graph G = (V, E) assigns a color c(v) ∈ {1, 2, ..., k} to each vertex v ∈ V, such that each non-isolated
Acyclic coloring
In graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic. The acyclic chromatic number A(G) of a graph G is the fewest colors needed in any acy
Star coloring
In the mathematical field of graph theory, a star coloring of a graph G is a (proper) vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star
De Bruijn–Erdős theorem (graph theory)
In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colo
Misra & Gries edge coloring algorithm
The Misra & Gries edge coloring algorithm is a polynomial time algorithm in graph theory that finds an edge coloring of any graph. The coloring produced uses at most colors, where is the maximum degre
Sum coloring
In graph theory, a sum coloring of a graph is a labeling of its vertices by positive integers, with no two adjacent vertices having equal labels, that minimizes the sum of the labels. The minimum sum
Cocoloring
In graph theory, a cocoloring of a graph G is an assignment of colors to the vertices such that each color class forms an independent set in G or in the complement of G. The cochromatic number z(G) of
Gyárfás–Sumner conjecture
In graph theory, the Gyárfás–Sumner conjecture asks whether, for every tree and complete graph , the graphs with neither nor as induced subgraphs can be properly colored using only a constant number o
Hadwiger conjecture (graph theory)
In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-c
Cereceda's conjecture
In the mathematics of graph coloring, Cereceda’s conjecture is an unsolved problem on the distance between pairs of colorings of sparse graphs. It states that, for two different colorings of a graph o
Thue number
In the mathematical area of graph theory, the Thue number of a graph is a variation of the chromatic index, defined by and named after mathematician Axel Thue, who studied the squarefree words used to
L(2,1)-coloring
L(2, 1)-coloring is a particular case of L(h, k)-coloring. In an L(2, 1)-coloring of a graph, G, the vertices of G are assigned color numbers in such a way that adjacent vertices get labels that diffe
Harmonious coloring
In graph theory, a harmonious coloring is a (proper) vertex coloring in which every pair of colors appears on at most one pair of adjacent vertices. It is the opposite of the complete coloring, which
Multi-trials technique
The multi-trials technique by Schneider et al. is employed for distributed algorithms and allows breaking of symmetry efficiently. Symmetry breaking is necessary, for instance, in resource allocation
B-coloring
In graph theory, a b-coloring of a graph is a coloring of the vertices where each color class contains a vertex that has a neighbor in all other color classes. The b-chromatic number of a G graph is t
Critical graph
In graph theory, a critical graph is an undirected graph all of whose subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deleti
Recursive largest first algorithm
The Recursive Largest First (RLF) algorithm is a heuristic for the NP-hard graph coloring problem. It was originally proposed by Frank Leighton in 1979. The RLF algorithm assigns colors to a graph’s v
Graph coloring game
The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players u
Total coloring
In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that
Equitable coloring
In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that
* No two adjacent vertices have the same color, an
Grötzsch's theorem
In the mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-free planar graph can be colored with only three colors. According to the four-color theorem, every g
Greedy coloring
In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that conside
T-coloring
In graph theory, a T-Coloring of a graph , given the set T of nonnegative integers containing 0, is a function that maps each vertex to a positive integer (color) such that if u and w are adjacent the
Hamiltonian coloring
Hamiltonian coloring, named after William Rowan Hamilton, is a type of graph coloring. Hamiltonian coloring uses a concept called detour distance between two vertices of the graph. It has many applica
Strong coloring
In graph theory, a strong coloring, with respect to a partition of the vertices into (disjoint) subsets of equal sizes, is a (proper) vertex coloring in which every color appears exactly once in every
Col (game)
Col is a pencil and paper game, specifically a map-coloring game, involving the shading of areas in a line drawing according to the rules of graph coloring. With each move, the graph must remain prope
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest
Four color theorem
In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same c
Distinguishing coloring
In graph theory, a distinguishing coloring or distinguishing labeling of a graph is an assignment of colors or labels to the vertices of the graph that destroys all of the nontrivial symmetries of the