Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Install
Faster access than browser!
 

Graph coloring

Index 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. [1]

195 relations: ACM SIGACT, Acyclic coloring, Acyclic orientation, Adjacent-vertex-distinguishing-total coloring, Albertson conjecture, Alfred Kempe, Algebraic graph theory, Approximation algorithm, Arthur Cayley, Augustus De Morgan, Axiom of choice, B-coloring, Bandwidth allocation, Bipartite graph, Boolean satisfiability problem, Branch and bound, Breadth-first search, Bridge (graph theory), Brooks' theorem, Brute-force search, Canadian Journal of Mathematics, Chordal graph, Chromatic polynomial, Circular coloring, Claude Berge, Claude Shannon, Clique (graph theory), Closed-form expression, Cocoloring, Communications of the ACM, Compiler, Complete coloring, Complete graph, Computer language, Computer program, Computers and Intractability, Critical graph, Crossing number (graph theory), Crown graph, Cubic graph, Cycle graph, Cycle rank, Daniel Brélaz, De Bruijn–Erdős theorem (graph theory), Defective coloring, Degree (graph theory), Depth-first search, Deterministic algorithm, Discrete Mathematics (journal), Distinguishing coloring, ..., Distributed algorithm, Dual graph, Dynamic programming, Edge coloring, Edge contraction, Elsevier, Equitable coloring, Erdős–Faber–Lovász conjecture, Euler characteristic, Exact coloring, Fibonacci number, Five color theorem, Four color theorem, Fractional coloring, Francis Guthrie, Friendship graph, Gain graph, Gallai–Hasse–Roy–Vitaver theorem, George David Birkhoff, Girth (graph theory), Glossary of graph theory terms, Graph (discrete mathematics), Graph automorphism, Graph coloring, Graph coloring game, Graph embedding, Graph homomorphism, Graph labeling, Graph minor, Graph theory, Grötzsch graph, Greedy algorithm, Greedy coloring, Group action, Grundy number, Hadwiger conjecture (graph theory), Hadwiger–Nelson problem, Hajós construction, Hamiltonian coloring, Harmonious coloring, Incidence coloring, Inclusion–exclusion principle, Independent set (graph theory), Indifference graph, Induced subgraph, Information and Computation, Information Processing Letters, Information theory, Interval edge coloring, Interval graph, Introduction to Algorithms, Isomorphism, Iterated logarithm, Karp's 21 NP-complete problems, Kőnig's theorem (graph theory), Kenneth Appel, L(2,1)-coloring, L(h, k)-coloring, Lecture Notes in Computer Science, Line graph, List coloring, List edge-coloring, List of unsolved problems in mathematics, London Mathematical Society, Longest path problem, Loop (graph theory), Lovász number, Maria Chudnovsky, Matching (graph theory), Mathematical Proceedings of the Cambridge Philosophical Society, Mathematics of Sudoku, Maximal independent set, Monochromatic triangle, Multi-trials technique, Multipartite graph, Mycielskian, Neil Robertson (mathematician), Nowhere-zero flow, NP (complexity), NP-completeness, NP-hardness, Null graph, Optimizing compiler, Oriented coloring, Path coloring, Pattern matching, Paul Seymour (mathematician), Percy John Heawood, Perfect graph, Perfectly orderable graph, Permutation, Petersen graph, Planar graph, Polynomial, Polynomial-time approximation scheme, Processor register, Programming Language Design and Implementation, Radio coloring, Ramsey theory, Rational point, Recurrence relation, Register allocation, Robin Thomas (mathematician), Royal Society, RP (complexity), Samuel Yates, Scheduling (computing), Semidefinite programming, Sharp-P-complete, SIAM Journal on Computing, SIAM Journal on Discrete Mathematics, Signed graph, Spanning tree, Springer Science+Business Media, Star (graph theory), Star coloring, Strong coloring, Strong perfect graph theorem, Subcoloring, Sudoku, Sum coloring, Symmetric graph, Symmetry breaking, Symposium on Foundations of Computer Science, Symposium on Parallelism in Algorithms and Architectures, Symposium on Principles of Distributed Computing, Symposium on Theory of Computing, T-coloring, Theory of Computing, Time complexity, Total coloring, Tree (graph theory), Tree-depth, Triangle-free graph, Tutte polynomial, Uniquely colorable graph, Unit disk graph, University College London, Uzi Vishkin, Vertex (graph theory), Vizing's theorem, W. T. Tutte, Weak coloring, William Rowan Hamilton, Wolfgang Haken. Expand index (145 more) »

ACM SIGACT

ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science.

New!!: Graph coloring and ACM SIGACT · See more »

Acyclic coloring

In graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic.

New!!: Graph coloring and Acyclic coloring · See more »

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.

New!!: Graph coloring and Acyclic orientation · See more »

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).

New!!: Graph coloring and Adjacent-vertex-distinguishing-total coloring · See more »

Albertson conjecture

In combinatorial mathematics, the Albertson conjecture is an unproven relationship between the crossing number and the chromatic number of a graph.

New!!: Graph coloring and Albertson conjecture · See more »

Alfred Kempe

Sir Alfred Bray Kempe DCL FRS (6 July 1849, Kensington, London – 21 April 1922, London) was a mathematician best known for his work on linkages and the four colour theorem.

New!!: Graph coloring and Alfred Kempe · See more »

Algebraic graph theory

Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs.

New!!: Graph coloring and Algebraic graph theory · See more »

Approximation algorithm

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to NP-hard optimization problems with provable guarantees on the distance of the returned solution to the optimal one.

New!!: Graph coloring and Approximation algorithm · See more »

Arthur Cayley

Arthur Cayley F.R.S. (16 August 1821 – 26 January 1895) was a British mathematician.

New!!: Graph coloring and Arthur Cayley · See more »

Augustus De Morgan

Augustus De Morgan (27 June 1806 – 18 March 1871) was a British mathematician and logician.

New!!: Graph coloring and Augustus De Morgan · See more »

Axiom of choice

In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that the Cartesian product of a collection of non-empty sets is non-empty.

New!!: Graph coloring and Axiom of choice · See more »

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.

New!!: Graph coloring and B-coloring · See more »

Bandwidth allocation

Bandwidth allocation is the process of assigning radio frequencies to different applications.

New!!: Graph coloring and Bandwidth allocation · See more »

Bipartite graph

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph.

New!!: Graph coloring and Bipartite graph · See more »

Boolean satisfiability problem

In computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated as SATISFIABILITY or SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula.

New!!: Graph coloring and Boolean satisfiability problem · See more »

Branch and bound

Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization.

New!!: Graph coloring and Branch and bound · See more »

Breadth-first search

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures.

New!!: Graph coloring and Breadth-first search · See more »

Bridge (graph theory)

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components.

New!!: Graph coloring and Bridge (graph theory) · See more »

Brooks' theorem

In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number.

New!!: Graph coloring and Brooks' theorem · See more »

Brute-force search

In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.

New!!: Graph coloring and Brute-force search · See more »

Canadian Journal of Mathematics

The Canadian Journal of Mathematics (Journal canadien de mathématiques; print:, online) is a bimonthly mathematics journal published by the Canadian Mathematical Society.

New!!: Graph coloring and Canadian Journal of Mathematics · See more »

Chordal graph

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle.

New!!: Graph coloring and Chordal graph · See more »

Chromatic polynomial

The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics.

New!!: Graph coloring and Chromatic polynomial · See more »

Circular coloring

In graph theory, circular coloring may be viewed as a refinement of usual graph coloring.

New!!: Graph coloring and Circular coloring · See more »

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.

New!!: Graph coloring and Claude Berge · See more »

Claude Shannon

Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American mathematician, electrical engineer, and cryptographer known as "the father of information theory".

New!!: Graph coloring and Claude Shannon · See more »

Clique (graph theory)

In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete.

New!!: Graph coloring and Clique (graph theory) · See more »

Closed-form expression

In mathematics, a closed-form expression is a mathematical expression that can be evaluated in a finite number of operations.

New!!: Graph coloring and Closed-form expression · See more »

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 G is the fewest colors needed in any cocolorings of G. The graphs with cochromatic number 2 are exactly the bipartite graphs, complements of bipartite graphs, and split graphs.

New!!: Graph coloring and Cocoloring · See more »

Communications of the ACM

Communications of the ACM is the monthly journal of the Association for Computing Machinery (ACM).

New!!: Graph coloring and Communications of the ACM · See more »

Compiler

A compiler is computer software that transforms computer code written in one programming language (the source language) into another programming language (the target language).

New!!: Graph coloring and Compiler · See more »

Complete coloring

In graph theory, complete coloring is the opposite of harmonious coloring in the sense that it is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices.

New!!: Graph coloring and Complete coloring · See more »

Complete graph

No description.

New!!: Graph coloring and Complete graph · See more »

Computer language

A computer language is a method of communication with a computer.

New!!: Graph coloring and Computer language · See more »

Computer program

A computer program is a collection of instructions for performing a specific task that is designed to solve a specific class of problems.

New!!: Graph coloring and Computer program · See more »

Computers and Intractability

In computer science, more specifically computational complexity theory, Computers and Intractability: A Guide to the Theory of NP-Completeness is an influential textbook by Michael Garey and David S. Johnson.

New!!: Graph coloring and Computers and Intractability · See more »

Critical graph

In graph theory, a critical graph is a graph G in which every vertex or edge is a critical element, that is, if its deletion decreases the chromatic number of G. Such a decrement can be not more than 1 in a graph.

New!!: Graph coloring and Critical graph · See more »

Crossing number (graph theory)

In graph theory, the crossing number of a graph is the lowest number of edge crossings of a plane drawing of the graph.

New!!: Graph coloring and Crossing number (graph theory) · See more »

Crown graph

No description.

New!!: Graph coloring and Crown graph · See more »

Cubic graph

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three.

New!!: Graph coloring and Cubic graph · See more »

Cycle graph

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 connected in a closed chain.

New!!: Graph coloring and Cycle graph · See more »

Cycle rank

In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi.

New!!: Graph coloring and Cycle rank · See more »

Daniel Brélaz

Daniel Brélaz (born on 4 January 1950, in Lausanne) is a Swiss politician, member of the Green Party of Switzerland and mayor of Lausanne between 2001 and 2016.

New!!: Graph coloring and Daniel Brélaz · See more »

De Bruijn–Erdős theorem (graph theory)

In graph theory, the De Bruijn–Erdős theorem states that, in graph coloring for an infinite graph, the number of colors needed is the same as the largest number of colors needed by any of its finite subgraphs (if this number is finite).

New!!: Graph coloring and De Bruijn–Erdős theorem (graph theory) · See more »

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.

New!!: Graph coloring and Defective coloring · See more »

Degree (graph theory)

In graph theory, the degree (or valency) of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice.

New!!: Graph coloring and Degree (graph theory) · See more »

Depth-first search

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.

New!!: Graph coloring and Depth-first search · See more »

Deterministic algorithm

In computer science, a deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states.

New!!: Graph coloring and Deterministic algorithm · See more »

Discrete Mathematics (journal)

Discrete Mathematics is a biweekly peer-reviewed scientific journal in the broad area of discrete mathematics, combinatorics, graph theory, and their applications.

New!!: Graph coloring and Discrete Mathematics (journal) · See more »

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 graph.

New!!: Graph coloring and Distinguishing coloring · See more »

Distributed algorithm

A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors.

New!!: Graph coloring and Distributed algorithm · See more »

Dual graph

In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of.

New!!: Graph coloring and Dual graph · See more »

Dynamic programming

Dynamic programming is both a mathematical optimization method and a computer programming method.

New!!: Graph coloring and Dynamic programming · See more »

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 adjacent edges have the same color.

New!!: Graph coloring and Edge coloring · See more »

Edge contraction

In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices that it previously joined.

New!!: Graph coloring and Edge contraction · See more »

Elsevier

Elsevier is an information and analytics company and one of the world's major providers of scientific, technical, and medical information.

New!!: Graph coloring and Elsevier · See more »

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.

New!!: Graph coloring and Equitable coloring · See more »

Erdős–Faber–Lovász conjecture

In graph theory, the Erdős–Faber–Lovász conjecture is an unsolved problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972.

New!!: Graph coloring and Erdős–Faber–Lovász conjecture · See more »

Euler characteristic

In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent.

New!!: Graph coloring and Euler characteristic · See more »

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.

New!!: Graph coloring and Exact coloring · See more »

Fibonacci number

In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones: Often, especially in modern usage, the sequence is extended by one more initial term: By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.

New!!: Graph coloring and Fibonacci number · See more »

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 counties of a state, the regions may be colored using no more than five colors in such a way that no two adjacent regions receive the same color.

New!!: Graph coloring and Five color theorem · See more »

Four color theorem

In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.

New!!: Graph coloring and Four color theorem · See more »

Fractional coloring

Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory.

New!!: Graph coloring and Fractional coloring · See more »

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.

New!!: Graph coloring and Francis Guthrie · See more »

Friendship graph

In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or n-fan) Fn is a planar undirected graph with 2n+1 vertices and 3n edges.

New!!: Graph coloring and Friendship graph · See more »

Gain graph

A gain graph is a graph whose edges are labelled "invertibly", or "orientably", by elements of a group G. This means that, if an edge e in one direction has label g (a group element), then in the other direction it has label g −1.

New!!: Graph coloring and Gain graph · See more »

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.

New!!: Graph coloring and Gallai–Hasse–Roy–Vitaver theorem · See more »

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.

New!!: Graph coloring and George David Birkhoff · See more »

Girth (graph theory)

In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph.

New!!: Graph coloring and Girth (graph theory) · See more »

Glossary of graph theory terms

This is a glossary of graph theory terms.

New!!: Graph coloring and Glossary of graph theory terms · See more »

Graph (discrete mathematics)

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".

New!!: Graph coloring and Graph (discrete mathematics) · See more »

Graph automorphism

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.

New!!: Graph coloring and Graph automorphism · See more »

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.

New!!: Graph coloring and Graph coloring · See more »

Graph coloring game

The graph coloring game is a mathematical game related to graph theory.

New!!: Graph coloring and Graph coloring game · See more »

Graph embedding

In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs (homeomorphic images of) are associated with edges in such a way that.

New!!: Graph coloring and Graph embedding · See more »

Graph homomorphism

In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure.

New!!: Graph coloring and Graph homomorphism · See more »

Graph labeling

In the mathematical discipline of graph theory, a graph labeling is the assignment of labels, traditionally represented by integers, to the edges or vertices, or both, of a graph.

New!!: Graph coloring and Graph labeling · See more »

Graph minor

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.

New!!: Graph coloring and Graph minor · See more »

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

New!!: Graph coloring and Graph theory · See more »

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.

New!!: Graph coloring and Grötzsch graph · See more »

Greedy algorithm

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum.

New!!: Graph coloring and Greedy algorithm · See more »

Greedy coloring

In the study of graph coloring problems in mathematics and computer science, a greedy coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color.

New!!: Graph coloring and Greedy coloring · See more »

Group action

In mathematics, an action of a group is a formal way of interpreting the manner in which the elements of the group correspond to transformations of some space in a way that preserves the structure of that space.

New!!: Graph coloring and Group action · See more »

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 graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible.

New!!: Graph coloring and Grundy number · See more »

Hadwiger conjecture (graph theory)

In graph theory, the Hadwiger conjecture (or Hadwiger's conjecture) states that, if all proper colorings of an undirected graph G use k or more colors, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph.

New!!: Graph coloring and Hadwiger conjecture (graph theory) · See more »

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 distance 1 from each other have the same color.

New!!: Graph coloring and Hadwiger–Nelson problem · See more »

Hajós construction

In graph theory, a branch of mathematics, the Hajós construction is an operation on graphs named after that may be used to construct any critical graph or any graph whose chromatic number is at least some given threshold.

New!!: Graph coloring and Hajós construction · See more »

Hamiltonian coloring

Hamiltonian coloring is a type of graph coloring.

New!!: Graph coloring and Hamiltonian coloring · See more »

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.

New!!: Graph coloring and Harmonious coloring · See more »

Incidence coloring

In graph theory, coloring generally implies assignment of labels to vertices, edges or faces in a graph.

New!!: Graph coloring and Incidence coloring · See more »

Inclusion–exclusion principle

In combinatorics (combinatorial mathematics), the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as where A and B are two finite sets and |S| indicates the cardinality of a set S (which may be considered as the number of elements of the set, if the set is finite).

New!!: Graph coloring and Inclusion–exclusion principle · See more »

Independent set (graph theory)

In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent.

New!!: Graph coloring and Independent set (graph theory) · See more »

Indifference graph

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other.

New!!: Graph coloring and Indifference graph · See more »

Induced subgraph

In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset.

New!!: Graph coloring and Induced subgraph · See more »

Information and Computation

Information and Computation is a computer science journal published by Elsevier (formerly Academic Press).

New!!: Graph coloring and Information and Computation · See more »

Information Processing Letters

Information Processing Letters is a peer reviewed scientific journal in the field of computer science, published by Elsevier.

New!!: Graph coloring and Information Processing Letters · See more »

Information theory

Information theory studies the quantification, storage, and communication of information.

New!!: Graph coloring and Information theory · See more »

Interval edge coloring

Interval edge coloring is a type of edge coloring in which edges are colored such that they form a set of intervals and each color in the interval set is at least used once to color the edges of the graph.It is to be noted that at each vertex in the graph the colors used form a consecutive set of natural numbers.

New!!: Graph coloring and Interval edge coloring · See more »

Interval graph

In graph theory, an interval graph is the intersection graph of a family of intervals on the real line.

New!!: Graph coloring and Interval graph · See more »

Introduction to Algorithms

Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

New!!: Graph coloring and Introduction to Algorithms · See more »

Isomorphism

In mathematics, an isomorphism (from the Ancient Greek: ἴσος isos "equal", and μορφή morphe "form" or "shape") is a homomorphism or morphism (i.e. a mathematical mapping) that can be reversed by an inverse morphism.

New!!: Graph coloring and Isomorphism · See more »

Iterated logarithm

In computer science, the iterated logarithm of n, written n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1.

New!!: Graph coloring and Iterated logarithm · See more »

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.

New!!: Graph coloring and Karp's 21 NP-complete problems · See more »

Kőnig's theorem (graph theory)

In the mathematical area of graph theory, Kőnig's theorem, proved by, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs.

New!!: Graph coloring and Kőnig's theorem (graph theory) · See more »

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 four-color theorem.

New!!: Graph coloring and Kenneth Appel · See more »

L(2,1)-coloring

L(2, 1)-coloring is a particular case of L(h, k)-coloring which is in fact a proper coloring.

New!!: Graph coloring and L(2,1)-coloring · See more »

L(h, k)-coloring

L(h, k) coloring in graph theory, is a (proper) vertex coloring in which every pair of adjacent vertices has color numbers that differ by at least h, and any pair of vertices at distance 2 have their colors differ by at least k. When h.

New!!: Graph coloring and L(h, k)-coloring · See more »

Lecture Notes in Computer Science

Springer Lecture Notes in Computer Science (LNCS) is a series of computer science books published by Springer Science+Business Media (formerly Springer-Verlag) since 1973.

New!!: Graph coloring and Lecture Notes in Computer Science · See more »

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name line graph comes from a paper by although both and used the construction before this.

New!!: Graph coloring and Line graph · See more »

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.

New!!: Graph coloring and List coloring · See more »

List edge-coloring

In mathematics, list edge-coloring is a type of graph coloring that combines list coloring and edge coloring.

New!!: Graph coloring and List edge-coloring · See more »

List of unsolved problems in mathematics

Since the Renaissance, every century has seen the solution of more mathematical problems than the century before, and yet many mathematical problems, both major and minor, still remain unsolved.

New!!: Graph coloring and List of unsolved problems in mathematics · See more »

London Mathematical Society

The London Mathematical Society (LMS) is one of the United Kingdom's learned societies for mathematics (the others being the Royal Statistical Society (RSS) and the Institute of Mathematics and its Applications (IMA)).

New!!: Graph coloring and London Mathematical Society · See more »

Longest path problem

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.

New!!: Graph coloring and Longest path problem · See more »

Loop (graph theory)

In graph theory, a loop (also called a self-loop or a "buckle") is an edge that connects a vertex to itself.

New!!: Graph coloring and Loop (graph theory) · See more »

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.

New!!: Graph coloring and Lovász number · See more »

Maria Chudnovsky

Maria Chudnovsky (born January 6, 1977) is an Israeli-American mathematician working on graph theory and combinatorial optimization.

New!!: Graph coloring and Maria Chudnovsky · See more »

Matching (graph theory)

In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices.

New!!: Graph coloring and Matching (graph theory) · See more »

Mathematical Proceedings of the Cambridge Philosophical Society

Mathematical Proceedings of the Cambridge Philosophical Society is a mathematical journal published by Cambridge University Press for the Cambridge Philosophical Society.

New!!: Graph coloring and Mathematical Proceedings of the Cambridge Philosophical Society · See more »

Mathematics of Sudoku

The class of Sudoku puzzles consists of a partially completed row-column grid of cells partitioned into N regions each of size N cells, to be filled in ("solved") using a prescribed set of N distinct symbols (typically the numbers), so that each row, column and region contains exactly one of each element of the set.

New!!: Graph coloring and Mathematics of Sudoku · See more »

Maximal independent set

In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set.

New!!: Graph coloring and Maximal independent set · See more »

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-free subgraphs.

New!!: Graph coloring and Monochromatic triangle · See more »

Multi-trials technique

The multi-trials technique by Schneider et al.

New!!: Graph coloring and Multi-trials technique · See more »

Multipartite graph

In graph theory, a part of mathematics, a k-partite graph is a graph whose vertices are or can be partitioned into k different independent sets.

New!!: Graph coloring and Multipartite graph · See more »

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.

New!!: Graph coloring and Mycielskian · See more »

Neil Robertson (mathematician)

George Neil Robertson (born November 30, 1938) is a mathematician working mainly in topological graph theory, currently a distinguished professor emeritus at the Ohio State University.

New!!: Graph coloring and Neil Robertson (mathematician) · See more »

Nowhere-zero flow

In graph theory, nowhere-zero flows are a special type of network flow which is related (by duality) to coloring planar graphs.

New!!: Graph coloring and Nowhere-zero flow · See more »

NP (complexity)

In computational complexity theory, NP (for nondeterministic polynomial time) is a complexity class used to describe certain types of decision problems.

New!!: Graph coloring and NP (complexity) · See more »

NP-completeness

In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.

New!!: Graph coloring and NP-completeness · See more »

NP-hardness

NP-hardness (''n''on-deterministic ''p''olynomial-time hardness), in computational complexity theory, is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP".

New!!: Graph coloring and NP-hardness · See more »

Null 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").

New!!: Graph coloring and Null graph · See more »

Optimizing compiler

In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program.

New!!: Graph coloring and Optimizing compiler · See more »

Oriented coloring

In graph theory, oriented graph coloring is a special type of graph coloring.

New!!: Graph coloring and Oriented coloring · See more »

Path coloring

In graph theory, path coloring usually refers to one of two problems.

New!!: Graph coloring and Path coloring · See more »

Pattern matching

In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern.

New!!: Graph coloring and Pattern matching · See more »

Paul Seymour (mathematician)

Paul Seymour (born July 26, 1950) is currently a professor at Princeton University; half in the department of mathematics and half in the program in applied and computational math.

New!!: Graph coloring and Paul Seymour (mathematician) · See more »

Percy John Heawood

Percy John Heawood (8 September 1861 Newport, Shropshire, England – 24 January 1955 Durham, England) was a British mathematician educated at Queen Elizabeth's School, Ipswich, and Exeter College, Oxford.

New!!: Graph coloring and Percy John Heawood · See more »

Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph.

New!!: Graph coloring and Perfect graph · See more »

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 given graph.

New!!: Graph coloring and Perfectly orderable graph · See more »

Permutation

In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting.

New!!: Graph coloring and Permutation · See more »

Petersen graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges.

New!!: Graph coloring and Petersen graph · See more »

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.

New!!: Graph coloring and Planar graph · See more »

Polynomial

In mathematics, a polynomial is an expression consisting of variables (also called indeterminates) and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponents of variables.

New!!: Graph coloring and Polynomial · See more »

Polynomial-time approximation scheme

In computer science, a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).

New!!: Graph coloring and Polynomial-time approximation scheme · See more »

Processor register

In computer architecture, a processor register is a quickly accessible location available to a computer's central processing unit (CPU).

New!!: Graph coloring and Processor register · See more »

Programming Language Design and Implementation

Programming Language Design and Implementation (PLDI) is one of the ACM SIGPLAN's most important conferences.

New!!: Graph coloring and Programming Language Design and Implementation · See more »

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 graphs such that the labels of adjacent vertices differ by at least two, and the labels of vertices at distance two from each other differ by at least one.

New!!: Graph coloring and Radio coloring · See more »

Ramsey theory

Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear.

New!!: Graph coloring and Ramsey theory · See more »

Rational point

In number theory and algebraic geometry, a rational point of an algebraic variety is a solution of a set of polynomial equations in a given field.

New!!: Graph coloring and Rational point · See more »

Recurrence relation

In mathematics, a recurrence relation is an equation that recursively defines a sequence or multidimensional array of values, once one or more initial terms are given: each further term of the sequence or array is defined as a function of the preceding terms.

New!!: Graph coloring and Recurrence relation · See more »

Register allocation

In compiler optimization, register allocation is the process of assigning a large number of target program variables onto a small number of CPU registers.

New!!: Graph coloring and Register allocation · See more »

Robin Thomas (mathematician)

Robin Thomas is a mathematician working in graph theory at the Georgia Institute of Technology.

New!!: Graph coloring and Robin Thomas (mathematician) · See more »

Royal Society

The President, Council and Fellows of the Royal Society of London for Improving Natural Knowledge, commonly known as the Royal Society, is a learned society.

New!!: Graph coloring and Royal Society · See more »

RP (complexity)

In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties.

New!!: Graph coloring and RP (complexity) · See more »

Samuel Yates

Samuel Yates (May 10, 1919 in Savannah, Georgia – April 22, 1991 in New Brunswick, NJ) was a computer engineer and mathematician who first described unique primes in the 1980s.

New!!: Graph coloring and Samuel Yates · See more »

Scheduling (computing)

In computing, scheduling is the method by which work specified by some means is assigned to resources that complete the work.

New!!: Graph coloring and Scheduling (computing) · See more »

Semidefinite programming

Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize) over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron.

New!!: Graph coloring and Semidefinite programming · See more »

Sharp-P-complete

#P-complete, pronounced "sharp P complete" or "number P complete" is a complexity class in computational complexity theory.

New!!: Graph coloring and Sharp-P-complete · See more »

SIAM Journal on Computing

The SIAM Journal on Computing is a scientific journal focusing on the mathematical and formal aspects of computer science.

New!!: Graph coloring and SIAM Journal on Computing · See more »

SIAM Journal on Discrete Mathematics

SIAM Journal on Discrete Mathematics is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM).

New!!: Graph coloring and SIAM Journal on Discrete Mathematics · See more »

Signed graph

In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign.

New!!: Graph coloring and Signed graph · See more »

Spanning tree

In the mathematical field of graph theory, a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges.

New!!: Graph coloring and Spanning tree · See more »

Springer Science+Business Media

Springer Science+Business Media or Springer, part of Springer Nature since 2015, is a global publishing company that publishes books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.

New!!: Graph coloring and Springer Science+Business Media · See more »

Star (graph theory)

In graph theory, a star Sk is the complete bipartite graph K1,k: a tree with one internal node and k leaves (but, no internal nodes and k + 1 leaves when k ≤ 1).

New!!: Graph coloring and Star (graph theory) · See more »

Star coloring

In graph-theoretic mathematics, 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.

New!!: Graph coloring and Star coloring · See more »

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 partition.

New!!: Graph coloring and Strong coloring · See more »

Strong perfect graph theorem

In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes (odd-length induced cycles) nor odd antiholes (complements of odd holes).

New!!: Graph coloring and Strong perfect graph theorem · See more »

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.

New!!: Graph coloring and Subcoloring · See more »

Sudoku

(originally called Number Place) is a logic-based, combinatorial number-placement puzzle.

New!!: Graph coloring and Sudoku · See more »

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.

New!!: Graph coloring and Sum coloring · See more »

Symmetric graph

In the mathematical field of graph theory, a graph G is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphism such that In other words, a graph is symmetric if its automorphism group acts transitively upon ordered pairs of adjacent vertices (that is, upon edges considered as having a direction).

New!!: Graph coloring and Symmetric graph · See more »

Symmetry breaking

In physics, symmetry breaking is a phenomenon in which (infinitesimally) small fluctuations acting on a system crossing a critical point decide the system's fate, by determining which branch of a bifurcation is taken.

New!!: Graph coloring and Symmetry breaking · See more »

Symposium on Foundations of Computer Science

The IEEE Annual Symposium on Foundations of Computer Science (FOCS) is an academic conference in the field of theoretical computer science.

New!!: Graph coloring and Symposium on Foundations of Computer Science · See more »

Symposium on Parallelism in Algorithms and Architectures

SPAA, the ACM Symposium on Parallelism in Algorithms and Architectures, is an academic conference in the fields of parallel computing and distributed computing.

New!!: Graph coloring and Symposium on Parallelism in Algorithms and Architectures · See more »

Symposium on Principles of Distributed Computing

The Symposium on Principles of Distributed Computing (PODC) is an academic conference in the field of distributed computing organised annually by the Association for Computing Machinery (special interest groups SIGACT and SIGOPS).

New!!: Graph coloring and Symposium on Principles of Distributed Computing · See more »

Symposium on Theory of Computing

The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science.

New!!: Graph coloring and Symposium on Theory of Computing · See more »

T-coloring

In graph theory, a T-Coloring of a graph G.

New!!: Graph coloring and T-coloring · See more »

Theory of Computing

Theory of Computing is a peer-reviewed open access scientific journal covering theoretical computer science.

New!!: Graph coloring and Theory of Computing · See more »

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.

New!!: Graph coloring and Time complexity · See more »

Total coloring

In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph.

New!!: Graph coloring and Total coloring · See more »

Tree (graph theory)

In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path.

New!!: Graph coloring and Tree (graph theory) · See more »

Tree-depth

In graph theory, the tree-depth of a connected undirected graph G is a numerical invariant of G, the minimum height of a Trémaux tree for a supergraph of G. This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages.

New!!: Graph coloring and Tree-depth · See more »

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.

New!!: Graph coloring and Triangle-free graph · See more »

Tutte polynomial

The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial.

New!!: Graph coloring and Tutte polynomial · See more »

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.

New!!: Graph coloring and Uniquely colorable graph · See more »

Unit disk graph

In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane.

New!!: Graph coloring and Unit disk graph · See more »

University College London

University College London (UCL) is a public research university in London, England, and a constituent college of the federal University of London.

New!!: Graph coloring and University College London · See more »

Uzi Vishkin

Uzi Vishkin (born 1953) is a computer scientist at the University of Maryland, College Park, where he is Professor of Electrical and Computer Engineering at the University of Maryland Institute for Advanced Computer Studies (UMIACS).

New!!: Graph coloring and Uzi Vishkin · See more »

Vertex (graph theory)

In mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices).

New!!: Graph coloring and Vertex (graph theory) · See more »

Vizing's theorem

In graph theory, Vizing's theorem (named for Vadim G. Vizing who published it in 1964) 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.

New!!: Graph coloring and Vizing's theorem · See more »

W. T. Tutte

William Thomas "Bill" Tutte OC FRS FRSC (14 May 1917 – 2 May 2002) was a British codebreaker and mathematician.

New!!: Graph coloring and W. T. Tutte · See more »

Weak coloring

In graph theory, a weak coloring is a special case of a graph labeling.

New!!: Graph coloring and Weak coloring · See more »

William Rowan Hamilton

Sir William Rowan Hamilton MRIA (4 August 1805 – 2 September 1865) was an Irish mathematician who made important contributions to classical mechanics, optics, and algebra.

New!!: Graph coloring and William Rowan Hamilton · See more »

Wolfgang Haken

Wolfgang Haken (born June 21, 1928 in Berlin, Germany) is a mathematician who specializes in topology, in particular 3-manifolds.

New!!: Graph coloring and Wolfgang Haken · See more »

Redirects here:

3-colorability, 3-colourability, 3-colouring, Algorithms for graph coloring, Applications of graph coloring, Chromatic number, Cole-Vishkin algorithm, Cole–Vishkin algorithm, Colored graph, Coloring algorithm, Coloring problem, Colourability, Colouring algorithm, Colouring problem, Distributed graph coloring, Face coloring, Graph Colouring, Graph Two-Coloring, Graph color, Graph coloration, Graph coloring algorithm, Graph coloring problem, Graph colouring, Graph colouring problem, Graph colouring problems, Graph two-coloring, K-chromatic graph, K-colorable, K-coloring, K-colouring, K-vertex colorable, Mycielski's theorem, Network coloring, Network colouring, Parallel algorithms for graph coloring, Proper coloring, Three-Colorable Graph, Three-colorable graph, Two-colorable graph, Unlabeled coloring, Vector chromatic number, Vertex chromatic number, Vertex color, Vertex coloring, Vertex colouring, Vertex-colouring.

References

[1] https://en.wikipedia.org/wiki/Graph_coloring

OutgoingIncoming
Hey! We are on Facebook now! »