Fractional coloring

Fractional coloring

. A 4:2-coloring ofthis graph does not exist.]

Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory.It differs from the traditional graph coloring in the sense that it assigns sets of colors instead of colors to elements. It can be viewed as the linear programming relaxation of traditional graph coloring.

A "b"-fold coloring of a graph "G" is an assignment of sets of size "b" to vertices of a graph such that adjacent vertices receive disjoint sets.An "a":"b"-coloring is a "b"-fold coloring out of "a" available colors.The "b"-fold chromatic number χ"b"("G") is the least "a" such that an "a":"b"-coloring exists.

The fractional chromatic number χf("G") is defined to be

:chi_{f}(G) = lim_{b o infty}frac{chi_{b}(G)}{b} = inf_{b}frac{chi_{b}(G)}{b}

Note that the limit exists because χ"b"("G") is "subadditive", meaning χ"a"+"b"("G") ≤ χ"a"("G") + χ"b"("G").

Some properties of χ"f"("G"):

:chi_f(G)ge n(G)/alpha(G)and:omega(G) le chi_f(G) le chi(G)

Here n("G") is the order of "G", α("G") is the independence number, ω("G") is the clique number, and χ("G") is the chromatic number.

Linear Programming (LP) Formulation

The fractional chromatic number χf("G") of a graph "G" can also be obtained as a solution to a linear program. The linear program has a dual that calculates "fractional clique number", a relaxation to the rationals of the integer concept of clique number. The strong duality theorem of linear programming guarantees that solutions to both linear programs do exist. However, each linear program has size that is exponential in the number of vertices of "G", and computing the fractional chromatic number of a graph is NP-hard. This stands in contrast to the problem of fractionally coloring the edges of a graph, which can be solved in polynomial time thanks to the simple structure of the matching polytope.

References

* Scheinerman, Edward R.; Ullman, Daniel H. (1997). "Fractional graph theory". New York: Wiley-Interscience. ISBN 0-471-17864-0.

*Godsil, Ghris; Royle, Gordon (2001). " Algebraic Graph Theory". New York: Springer-Verlag. ISBN 0-387-95241-1.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. 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… …   Wikipedia

  • Edge coloring — A 3 edge coloring of the Desargues graph. 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. For example, the figure to the right shows an edge… …   Wikipedia

  • Total coloring — [ Proper total coloring of Foster Cage with 6 colors. The total chromatic number of this graph is 6 sincethe 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… …   Wikipedia

  • Linear programming relaxation — In mathematics, the linear programming relaxation of a 0 1 integer program is the problem that arises by replacing the constraint that each variable must be 0 or 1 by a weaker constraint, that each variable belong to the interval [0,1] .That is,… …   Wikipedia

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Unit disk graph — In geometric graph theory, a unit disk graph is the intersection graph of a family of unit circles in the Euclidean plane. That is, we form a vertex for each circle, and connect two vertices by an edge whenever the corresponding circles cross… …   Wikipedia

  • Linear programming — (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”