Content deleted Content added
Josh Parris (talk | contribs) m Robot-assisted disambiguation: Graph - Changed link(s) to Graph (mathematics) |
Added short description Tags: Mobile edit Mobile app edit Android app edit App description add |
||
| (10 intermediate revisions by 8 users not shown) | |||
Line 1:
{{Short description|Concept in the mathematics field of graph theory}}
In mathematics, the '''interval [[chromatic number]]''' ''X''<sub><</sub>(''H'') of an [[ordered graph]] ''H'' is the minimum number of intervals the (linearly ordered) vertex set of ''H'' can be [[partition of a set|partitioned]] into so that no two vertices belonging to the same interval are adjacent in ''H''.<ref>[[János Pach]], Gabor Tardos, "Forbidden Pattern and Unit Distances",page 1-9,2005,ACM.</ref>▼
{{one source |date=April 2024}}
▲In mathematics, the '''interval [[chromatic number]]''' ''X''<sub><</sub>(''H'') of an [[ordered graph]] ''H'' is the minimum number of intervals the (linearly ordered) vertex set of ''H'' can be [[partition of a set|partitioned]] into so that no two vertices belonging to the same interval are adjacent in ''H''.<ref>[[János Pach]], Gabor Tardos, "Forbidden Pattern and Unit Distances", page 1-9, 2005, ACM.</ref>
== Difference with chromatic number ==
Line 8 ⟶ 10:
''X''<sub><</sub>(''H'') ≥ K(''H'').
One thing to be noted, for a particular [[Graph (discrete mathematics)|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.
==References==
Line 14 ⟶ 16:
[[Category:Graph coloring]]
{{graph-stub}}
| |||