FACTOID # 19: Cheap sloppy joes: Looking for reduced-price lunches for schoolchildren? Head for Oklahoma!
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Total coloring
Proper total coloring of Foster Cage with 6 colors. The total chromatic number of this graph is 6 since the degree of each vertex is 5 (5 adjacent edges + 1 vertex=6).
Proper total coloring of Foster Cage with 6 colors. The total chromatic number of this graph is 6 since the degree of each vertex is 5 (5 adjacent edges + 1 vertex=6).

In graph theory, 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 incident edges, and no edge and its endvertices are assigned the same color. The total chromatic number χ″(G) a graph G is the least number of colors needed in any total coloring of G. Image File history File links Total_coloring_foster_cage. ... Image File history File links Total_coloring_foster_cage. ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ...


The total graph T = T(G) of a graph G is a graph such that (i) the vertex set of T corresponds to the vertices and edges of G and (ii) two vertices are adjacent in T if and only if their corresponding elements are either adjacent or incident in G. Then total coloring becomes a (proper) vertex coloring of the total graph. Image:3-colouringEx. ...


Some properties of χ″(G):

  1. χ″(G) ≥ Δ(G) + 1.
  2. χ″(G) ≤ Δ(G) + 1026. (Molloy, Reed 1998)
  3. χ″(G) ≤ Δ(G) + 8 ln8(Δ(G)) for sufficiently large Δ(G). (Hind, Molloy, Reed 1998)
  4. χ″(G) ≤ ch′(G) + 2.

Here Δ(G) is the maximum degree; and ch′(G), the edge choosability. Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... In mathematics, list edge-coloring is a type of graph coloring. ...


Total coloring arises naturally since it is simply a mix of vertex and edge colorings. The next step is to look for any Brooks-typed or Vizing-typed upper bound on the total chromatic number in terms of maximum degree. It turns out that the total coloring version of maximum degree upper bound is a difficult problem and has eluded mathematicians for 40 years. The most well-known speculation is the following. Image:3-colouringEx. ... In graph theory, as with its vertex counterpart, an edge coloring of a graph, when mentioned without any qualification, is always assumed to be a proper coloring of the edges, meaning no two adjacent edges are assigned the same color. ...


Total coloring conjecture. (Behzad, Vizing)

χ″(G) ≤ Δ(G) + 2.

Apparently, the term "total coloring" and the statement of total coloring conjecture were independently introduced by Behzad and Vizing in numerous occasions between 1964 and 1968. See [Jensen, Toft 1995] for details. The conjecture is known to hold for a few important classes of graphs, such as all bipartite graphs and most planar graphs except those with maximum degree 6. The planar case can be completed if Vizing's planar graph conjecture is true. Also, if the list coloring conjecture is true, then χ″(G) ≤ Δ(G) + 3. Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... In graph theory, as with its vertex counterpart, an edge coloring of a graph, when mentioned without any qualification, is always assumed to be a proper coloring of the edges, meaning no two adjacent edges are assigned the same color. ... In mathematics, list edge-coloring is a type of graph coloring. ...


Results related to total coloring have been obtained. For example, Kilakos and Reed (1993) proved that the fractional chromatic number of the total graph of a graph G is at most Δ(G) + 2. Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. ...


References

  • Hind, Hugh; Molloy, Michael; Reed, Bruce (1998). Total coloring with Δ + poly(logΔ) colors. SIAM J. Comput. 28(3), 816–821.
  • Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
  • Kilakos, Kyriakos; Reed, Bruce (1993). Fractionally colouring total graphs. Combinatorica 13, 435–440.
  • Molloy, Michael; Reed, Bruce (1998). A bound on the total chromatic number. Combinatorica 18, 241–280.

  Results from FactBites:
 
Graph coloring - Wikipedia, the free encyclopedia (1580 words)
Graph coloring is not to be confused with graph labeling, which is an assignment of labels, usually also in the form of numbers, to vertices or edges.
When used without any qualification, a coloring of a graph is always assumed to be a vertex coloring, namely an assignment of colors to the vertices of the graph.
A coloring using at most k colors is called a (proper) k-coloring and is equivalent to the problem of partitioning the vertex set into k or fewer independent sets.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m