Interval chromatic number of an ordered graph
- Interval chromatic number of an ordered graph
In mathematics, the interval chromatic number "X"<("H") of an ordered graph "H" is the minimum number of intervals the (linearly ordered) vertex set of "H" can be partitioned into so that no two vertices belonging to the same interval are adjacent in "H". [Janos Pach, Gabor Tardos, "Forbidden Pattern and Unit Distances",page 1-9,2005,ACM.]
Difference with chromatic number
It is interesting about interval chromatic number that it is easily computable. Indeed, by a simple greedy algorithm one can efficiently find an optimal partition of the vertex set of "H" into "X"<("H") independent intervals. This is in sharp contrast with the fact that even the approximation of the usual chromatic number of graph is an NP hard task.
Let "K"(H) is the chromatic number of any ordered graph "H". Then for any ordered graph "H","X"<("H") ≥ K("H").
One thing to be noted, for a particular graph "H" and its isomorphic graphs the chromatic number is same, but the interval chromatic number may differ. Actually it depends upon the ordering of the vertex set.
Reference
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
Clique (graph theory) — A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue … Wikipedia
Perfect graph — The Paley graph of order 9, colored with three colors and showing a clique of three vertices. In this graph and each of its induced subgraphs the chromatic number equals the clique number, so it is a perfect graph. In graph theory, a perfect… … Wikipedia
List of mathematics articles (I) — NOTOC Ia IA automorphism ICER Icosagon Icosahedral 120 cell Icosahedral prism Icosahedral symmetry Icosahedron Icosian Calculus Icosian game Icosidodecadodecahedron Icosidodecahedron Icositetrachoric honeycomb Icositruncated dodecadodecahedron… … Wikipedia
Geometric graph theory — In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs. Notable geometric… … 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
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
Список терминов, относящихся к алгоритмам и структурам данных — Это служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавливается на информационные списки и глоссарии … Википедия
Список терминов — Список терминов, относящихся к алгоритмам и структурам данных Это сл … Википедия
Dilworth's theorem — In mathematics, in the areas of order theory and combinatorics, Dilworth s theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician … Wikipedia
