![Petersen graph 3-coloring](https://upload.wikimedia.org/wikipedia/commons/9/90/Petersen_graph_3-coloring.svg)
In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, graph coloring is a special case of
graph labeling
In the mathematical discipline of graph theory, a graph labelling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph.
Formally, given a graph , a vertex labelling is a function of to a set o ...
; it is an assignment of labels traditionally called "colors" to elements of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
subject to certain constraints. In its simplest form, it is a way of coloring the
vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an
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 edge coloring of a graph by the colors red, blu ...
assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a
planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.
Vertex coloring is often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance. For example, an edge coloring of a graph is just a vertex coloring of its
line graph
In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...
, and a face coloring of a plane graph is just a vertex coloring of its
dual. However, non-vertex coloring problems are often stated and studied as-is. This is partly
pedagogical
Pedagogy (), most commonly understood as the approach to teaching, is the theory and practice of learning, and how this process influences, and is influenced by, the social, political and psychological development of learners. Pedagogy, taken as ...
, and partly because some problems are best studied in their non-vertex form, as in the case of edge coloring.
The convention of using colors originates from coloring the countries of a
map
A map is a symbolic depiction emphasizing relationships between elements of some space, such as objects, regions, or themes.
Many maps are static, fixed to paper or some other durable medium, while others are dynamic or interactive. Although ...
, where each face is literally colored. This was generalized to coloring the faces of a graph
embedded in the plane. By planar duality it became coloring the vertices, and in this form it generalizes to all graphs. In mathematical and computer representations, it is typical to use the first few positive or non-negative integers as the "colors". In general, one can use any
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. T ...
as the "color set". The nature of the coloring problem depends on the number of colors but not on what they are.
Graph coloring enjoys many practical applications as well as theoretical challenges. Beside the classical types of problems, different limitations can also be set on the graph, or on the way a color is assigned, or even on the color itself. It has even reached popularity with the general public in the form of the popular number puzzle
Sudoku
Sudoku (; ja, 数独, sūdoku, digit-single; originally called Number Place) is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row ...
. Graph coloring is still a very active field of research.
''Note: Many terms used in this article are defined in
Glossary of graph theory.''
History
The first results about graph coloring deal almost exclusively with
planar graphs in the form of the coloring of ''maps''.
While trying to color a map of the counties of England,
Francis Guthrie
Francis Guthrie (born 22 January 1831 in London; d. 19 October 1899 in Claremont, Cape Town) was a South African mathematician and botanist who first posed the Four Colour Problem in 1852. He studied mathematics under Augustus De Morgan, and ...
postulated the
four color conjecture, noting that four colors were sufficient to color the map so that no regions sharing a common border received the same color. Guthrie's brother passed on the question to his mathematics teacher
Augustus de Morgan at
University College
In a number of countries, a university college is a college institution that provides tertiary education but does not have full or independent university status. A university college is often part of a larger university. The precise usage varies ...
, who mentioned it in a letter to
William Hamilton in 1852.
Arthur Cayley raised the problem at a meeting of the
London Mathematical Society in 1879. The same year,
Alfred Kempe
Sir Alfred Bray Kempe FRS (6 July 1849 – 21 April 1922) was a mathematician best known for his work on linkages and the four colour theorem.
Biography
Kempe was the son of the Rector of St James's Church, Piccadilly, the Rev. John Edward K ...
published a paper that claimed to establish the result, and for a decade the four color problem was considered solved. For his accomplishment Kempe was elected a Fellow of the
Royal Society
The Royal Society, formally The Royal Society of London for Improving Natural Knowledge, is a learned society and the United Kingdom's national academy of sciences. The society fulfils a number of roles: promoting science and its benefits, re ...
and later President of the London Mathematical Society.
In 1890,
Heawood Heawood is a surname. Notable people with the surname include:
*Jonathan Heawood, British journalist
*Percy John Heawood (1861–1955), British mathematician
**Heawood conjecture
**Heawood graph
**Heawood number In mathematics, the Heawood number ...
pointed out that Kempe's argument was wrong. However, in that paper he proved the
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 five colors in such a way that no two adjacent reg ...
, saying that every planar map can be colored with no more than ''five'' colors, using ideas of Kempe. In the following century, a vast amount of work and theories were developed to reduce the number of colors to four, until the four color theorem was finally proved in 1976 by
Kenneth Appel
Kenneth Ira Appel (October 8, 1932 – April 19, 2013) was an American mathematician who in 1976, with colleague Wolfgang Haken at the University of Illinois at Urbana–Champaign, solved one of the most famous problems in mathematics, the fou ...
and
Wolfgang Haken
Wolfgang Haken (June 21, 1928 – October 2, 2022) was a German American mathematician who specialized in topology, in particular 3-manifolds.
Biography
Haken was born in Berlin, Germany. His father was Werner Haken, a physicist who had Max ...
. The proof went back to the ideas of Heawood and Kempe and largely disregarded the intervening developments. The proof of the four color theorem is also noteworthy for being the first major computer-aided proof.
In 1912,
George David Birkhoff
George David Birkhoff (March 21, 1884 – November 12, 1944) was an American mathematician best known for what is now called the ergodic theorem. Birkhoff was one of the most important leaders in American mathematics in his generation, and during ...
introduced the
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 originally defined by George David Birkhoff to s ...
to study the coloring problems, which was generalised to the
Tutte polynomial
The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contai ...
by
Tutte
William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a majo ...
, important structures in
algebraic graph theory
Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches. There are three main branches of algebraic graph th ...
. Kempe had already drawn attention to the general, non-planar case in 1879, and many results on generalisations of planar graph coloring to surfaces of higher order followed in the early 20th century.
In 1960,
Claude Berge
Claude Jacques Berge (5 June 1926 – 30 June 2002) was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory.
Biography and professional history
Claude Berge's parents were André Berge and Geneviève ...
formulated another conjecture about graph coloring, the ''strong perfect graph conjecture'', originally motivated by an
information-theoretic
Information theory is the scientific study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. T ...
concept called the
zero-error capacity of a graph introduced by
Shannon. The conjecture remained unresolved for 40 years, until it was established as the celebrated
strong perfect graph theorem by
Chudnovsky,
Robertson
Robertson may refer to:
People
* Robertson (surname) (includes a list of people with this name)
* Robertson (given name)
* Clan Robertson, a Scottish clan
* Robertson, stage name of Belgian magician Étienne-Gaspard Robert (1763–1837)
Places ...
,
Seymour, and
Thomas
Thomas may refer to:
People
* List of people with given name Thomas
* Thomas (name)
* Thomas (surname)
* Saint Thomas (disambiguation)
* Thomas Aquinas (1225–1274) Italian Dominican friar, philosopher, and Doctor of the Church
* Thomas the A ...
in 2002.
Graph coloring has been studied as an algorithmic problem since the early 1970s: the chromatic number problem (see
below) is one of
Karp's 21 NP-complete problems
In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete. In his 1972 paper, "Reducibility Among Combinatorial Problems", Richard Karp used Stephen Cook's 1971 theorem that the b ...
from 1972, and at approximately the same time various exponential-time algorithms were developed based on backtracking and on the deletion-contraction recurrence of . One of the major applications of graph coloring,
register allocation
In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers.
Register allocation can happen over a basic block (''local register allocatio ...
in compilers, was introduced in 1981.
Definition and terminology
Vertex coloring
When used without any qualification, a coloring of a graph is almost always a ''proper vertex coloring'', namely a labeling of the graph's vertices with colors such that no two vertices sharing the same
edge
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed ...
have the same color. Since a vertex with a
loop
Loop or LOOP may refer to:
Brands and enterprises
* Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live
* Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets
* Loop Mobile, an ...
(i.e. a connection directly back to itself) could never be properly colored, it is understood that graphs in this context are loopless.
The terminology of using ''colors'' for vertex labels goes back to map coloring. Labels like ''red'' and ''blue'' are only used when the number of colors is small, and normally it is understood that the labels are drawn from the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s
A coloring using at most colors is called a (proper) -coloring. The smallest number of colors needed to color a graph is called its chromatic number, and is often denoted . Sometimes is used, since is also used to denote the
Euler characteristic of a graph. A graph that can be assigned a (proper) -coloring is -colorable, and it is -chromatic if its chromatic number is exactly . A subset of vertices assigned to the same color is called a ''color class'', every such class forms an
independent set. Thus, a -coloring is the same as a partition of the vertex set into independent sets, and the terms ''-partite'' and ''-colorable'' have the same meaning.
Chromatic polynomial
![Chromatic polynomial of all 3-vertex graphs](https://upload.wikimedia.org/wikipedia/commons/b/b6/Chromatic_polynomial_of_all_3-vertex_graphs.png)
The chromatic polynomial counts the number of ways a graph can be colored using some of a given number of colors. For example, using three colors, the graph in the adjacent image can be colored in 12 ways. With only two colors, it cannot be colored at all. With four colors, it can be colored in 24 + 4⋅12 = 72 ways: using all four colors, there are 4! = 24 valid colorings (''every'' assignment of four colors to ''any'' 4-vertex graph is a proper coloring); and for every choice of three of the four colors, there are 12 valid 3-colorings. So, for the graph in the example, a table of the number of valid colorings would start like this:
The chromatic polynomial is a function that counts the number of -colorings of . As the name indicates, for a given the function is indeed a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
in . For the example graph, , and indeed .
The chromatic polynomial includes more information about the colorability of than does the chromatic number. Indeed, is the smallest positive integer that is not a zero of the chromatic polynomial
Edge coloring
An edge coloring of a graph is a proper coloring of the ''edges'', meaning an assignment of colors to edges so that no vertex is incident to two edges of the same color. An edge coloring with colors is called a -edge-coloring and is equivalent to the problem of partitioning the edge set into
matchings. The smallest number of colors needed for an edge coloring of a graph is the chromatic index, or edge chromatic number, . A Tait coloring is a 3-edge coloring of a
cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.
A bicubic graph is a cubic bi ...
. The
four color theorem is equivalent to the assertion that every planar cubic
bridgeless graph admits a Tait coloring.
Total coloring
Total coloring is a type of 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 no adjacent vertices, no adjacent edges, and no edge and its end-vertices are assigned the same color. The total chromatic number of a graph is the fewest colors needed in any total coloring of .
Unlabeled coloring
An unlabeled coloring of a graph is an
orbit
In celestial mechanics, an orbit is the curved trajectory of an object such as the trajectory of a planet around a star, or of a natural satellite around a planet, or of an artificial satellite around an object or position in space such as ...
of a coloring under the action of the
automorphism group
In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...
of the graph. Note that the colors remain labeled; it is the graph that is unlabeled.
There is an analogue of the
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 originally defined by George David Birkhoff to s ...
which counts the number of unlabeled colorings of a graph from a given finite color set.
If we interpret a coloring of a graph on vertices as a vector in , the action of an automorphism is a
permutation of the coefficients in the coloring vector.
Properties
Upper bounds on the chromatic number
Assigning distinct colors to distinct vertices always yields a proper coloring, so
:
The only graphs that can be 1-colored are
edgeless graph
In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").
Order-zero graph
The order-zero graph, , is th ...
s. A
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
of ''n'' vertices requires
colors. In an optimal coloring there must be at least one of the graph's ''m'' edges between every pair of color classes, so
:
If ''G'' contains a
clique
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
of size ''k'', then at least ''k'' colors are needed to color that clique; in other words, the chromatic number is at least the clique number:
:
For
perfect graph
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfe ...
s this bound is tight. Finding cliques is known as the
clique problem
In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cli ...
.
More generally a family
of graphs is
-bounded if there is some function
such that the graphs
in
can be colored with at most
colors, for the family of the perfect graphs this function is
.
The 2-colorable graphs are exactly the
bipartite graphs, including
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
s and forests.
By the four color theorem, every planar graph can be 4-colored.
A
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 considers the vertices of the graph in sequence an ...
shows that every graph can be colored with one more color than the maximum vertex
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
,
:
Complete graphs have
and
, and
odd cycle
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
s have
and
, so for these graphs this bound is best possible. In all other cases, the bound can be slightly improved;
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 Δ neighbors, the vertices can be colored with ...
states that
:
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 Δ neighbors, the vertices can be colored with ...
:
for a connected, simple graph ''G'', unless ''G'' is a complete graph or an odd cycle.
Lower bounds on the chromatic number
Several lower bounds for the chromatic bounds have been discovered over the years:
Hoffman's bound: Let
be a real symmetric matrix such that
whenever
is not an edge in
. Define
, where
are the largest and smallest eigenvalues of
. Define
, with
as above. Then:
:
: Let
be a positive semi-definite matrix such that
whenever
is an edge in
. Define
to be the least k for which such a matrix
exists. Then
:
Lovász number In graph theory, the Lovász number of a graph is a real number that is an upper bound on the Shannon capacity of the graph. It is also known as Lovász theta function and is commonly denoted by \vartheta(G), using a script form of the Greek letter ...
: The Lovász number of a complementary graph is also a lower bound on the chromatic number:
:
Fractional chromatic number
Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It is a generalization of ordinary graph coloring. In a traditional graph coloring, each vertex in a graph is assigned some color, and adjacent v ...
: The fractional chromatic number of a graph is a lower bound on the chromatic number as well:
:
These bounds are ordered as follows:
:
Graphs with high chromatic number
Graphs with large
cliques
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
have a high chromatic number, but the opposite is not true. The
Grötzsch graph
In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example ...
is an example of a 4-chromatic graph without a triangle, and the example can be generalized to the
Mycielskian
In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of . The construction preserves the property of being triangle-free but increases the chromatic ...
s.
: Theorem (, , ): There exist triangle-free graphs with arbitrarily high chromatic number.
To prove this, both, Mycielski and Zykov, each gave a construction of an inductively defined family of
triangle-free graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with g ...
s but with arbitrarily large chromatic number. Burling (1965) constructed axis aligned boxes in
whose
intersection graph
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
is triangle-free and requires arbitrarily many colors to be properly colored. This family of graphs is then called the Burling graphs. The same class of graphs is used for the construction of a family of triangle-free line segments in the plane, given by Pawlik et al. (2014).
It shows that the chromatic number of its intersection graph is arbitrarily large as well. Hence, this implies that axis aligned boxes in
as well as line segments in
are not
χ-bounded
In graph theory, a \chi-bounded family \mathcal of graphs is one for which there is some function c such that, for every integer t the graphs in \mathcal with t=\omega(G) (clique number) can be colored with at most c(t) colors. This concept and its ...
.
From Brooks's theorem, graphs with high chromatic number must have high maximum degree. But colorability is not an entirely local phenomenon: A graph with high
girth looks locally like a tree, because all cycles are long, but its chromatic number need not be 2:
:Theorem (
Erdős): There exist graphs of arbitrarily high girth and chromatic number.
Bounds on the chromatic index
An edge coloring of ''G'' is a vertex coloring of its
line graph
In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...
, and vice versa. Thus,
:
There is a strong relationship between edge colorability and the graph's maximum degree
. Since all edges incident to the same vertex need their own color, we have
:
Moreover,
:
Kőnig's theorem:
if ''G'' is bipartite.
In general, the relationship is even stronger than what Brooks's theorem gives for vertex coloring:
:
Vizing's Theorem: A graph of maximal degree
has edge-chromatic number
or
.
Other properties
A graph has a ''k''-coloring if and only if it has an
acyclic orientation
In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orie ...
for which the
longest path
In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called ''simple'' if it does not have any repeated vertices; the length of a path ma ...
has length at most ''k''; this is the
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 minimum number of colors needed to properly c ...
.
For planar graphs, vertex colorings are essentially dual to
nowhere-zero flows.
About infinite graphs, much less is known.
The following are two of the few results about infinite graph coloring:
*If all finite subgraphs of an
infinite graph
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A
B
...
''G'' are ''k''-colorable, then so is ''G'', under the assumption of the
axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
. This is the
de Bruijn–Erdős theorem of .
*If a graph admits a full ''n''-coloring for every ''n'' ≥ ''n''
0, it admits an infinite full coloring .
Open problems
As stated above,
A conjecture of Reed from 1998 is that the value is essentially closer to the lower bound,
The
chromatic number of the plane, where two points are adjacent if they have unit distance, is unknown, although it is one of 5, 6, or 7. Other
open problems In science and mathematics, an open problem or an open question is a known problem which can be accurately stated, and which is assumed to have an objective and verifiable solution, but which has not yet been solved (i.e., no solution for it is kno ...
concerning the chromatic number of graphs include the
Hadwiger conjecture There are several conjectures known as the Hadwiger conjecture or Hadwiger's conjecture. They include:
* Hadwiger conjecture (graph theory), a relationship between the number of colors needed by a given graph and the size of its largest clique mino ...
stating that every graph with chromatic number ''k'' has a
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
on ''k'' vertices as a
minor, the
Erdős–Faber–Lovász conjecture bounding the chromatic number of unions of complete graphs that have at most one vertex in common to each pair, and the
Albertson conjecture that among ''k''-chromatic graphs the complete graphs are the ones with smallest
crossing number.
When Birkhoff and Lewis introduced the chromatic polynomial in their attack on the four-color theorem, they conjectured that for planar graphs ''G'', the polynomial
has no zeros in the region