About: Chromatic number

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Chromatic number Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FChromatic_number

Attributes	Values
rdfs:label	Chromatic number (en) Liczba chromatyczna (pl) Хроматическое число (ru) Хроматичне число (uk) 色数 (zh)
rdfs:comment	Хроматичне число графа G — мінімальна кількість кольорів, в які можна розфарбувати вершини графа G таким чином, щоб кінці будь-якого ребра мали різні кольори. Позначається як χ(G). (uk) Хромати́ческое число́ гра́фа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается χ(G). (ru) Liczba chromatyczna – liczba kolorów niezbędna do optymalnego klasycznego (wierzchołkowego) pokolorowania grafu, czyli najmniejsza możliwa liczba taka, że możliwe jest legalne pokolorowanie wierzchołków grafu Oznacza się ją symbolem . Problem wyznaczenia liczby chromatycznej jest NP-trudny – nie są znane niezawodne wielomianowe algorytmy wyznaczające liczbę chromatyczną każdego grafu. Istnieje jednak szereg oszacowań liczby chromatycznej dla różnych klas grafów, np.: (pl)
dcterms:subject	Graph invariants
Wikipage page ID	670588 (xsd:integer)
Wikipage revision ID	894539410 (xsd:integer)
Link from a Wikipage to another Wikipage	Graph invariants Graph coloring
Wikipage redirect	Graph coloring
sameAs	Chromatic number Chromatic number Chromatic number Chromatic number Chromatic number Chromatic number Chromatic number Chromatic number
dbp:wikiPageUsesTemplate	dbt:R_to_anchor dbt:R_with_possibilities dbt:Redirect_category_shell dbt:Wikidata-redirect
has abstract	Liczba chromatyczna – liczba kolorów niezbędna do optymalnego klasycznego (wierzchołkowego) pokolorowania grafu, czyli najmniejsza możliwa liczba taka, że możliwe jest legalne pokolorowanie wierzchołków grafu Oznacza się ją symbolem . Problem wyznaczenia liczby chromatycznej jest NP-trudny – nie są znane niezawodne wielomianowe algorytmy wyznaczające liczbę chromatyczną każdego grafu. Istnieje jednak szereg oszacowań liczby chromatycznej dla różnych klas grafów, np.: * gdzie jest rozmiarem maksymalnej kliki grafu * Twierdzenie Brooksa: dla grafów pełnych oraz cykli o nieparzystej długości gdzie jest maksymalnym stopniem wierzchołka w grafie G; dla pozostałych grafów spójnych zachodzi , * dla grafów planarnych * dla drzew o co najmniej dwóch wierzchołkach (pl) Хроматичне число графа G — мінімальна кількість кольорів, в які можна розфарбувати вершини графа G таким чином, щоб кінці будь-якого ребра мали різні кольори. Позначається як χ(G). (uk) Хромати́ческое число́ гра́фа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается χ(G). (ru)
prov:wasDerivedFrom	wikipedia-en:Chromatic_number?oldid=894539410&ns=0
page length (characters) of wiki page	181 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Chromatic_number
is Link from a Wikipage to another Wikipage of	Probabilistic method Queue number Mirsky's theorem Moser spindle Mycielskian Meredith graph Meringer graph Degeneracy (graph theory) Desargues graph Unit distance graph De Bruijn–Erdős theorem (graph theory) Degree (graph theory) Double-star snark Dyck graph Incidence poset Induced matching Interval chromatic number of an ordered graph Jan Mycielski Kőnig's theorem (graph theory) Lexicographic product of graphs List of graphs by edges and vertices Pseudorandom graph Robertson–Wegner graph Well-colored graph Zero-divisor graph 1-planar graph Crossing number (graph theory) S. A. Choudum Chi (letter) Ellingham–Horton graph Errera graph Generalized Petersen graph Geometric graph theory Neighbourhood (graph theory) Petersen graph Quantum pseudo-telepathy R. Leonard Brooks Clique problem Frankl–Rödl graph Friendship graph Gamma Girth (graph theory) Glossary of graph theory Graph (discrete mathematics) Graph bandwidth Graph homomorphism Graph power Graph removal lemma Bounded expansion Möbius ladder Critical graph Crossing Numbers of Graphs Equitable coloring Erdős–Stone theorem Linkless embedding Lonely runner conjecture Lovász number Star (graph theory) Claw-free graph Clebsch graph Clique (graph theory) Complement graph Franklin graph Frucht graph Hadwiger–Nelson problem Half graph Harries–Wong graph Horton graph

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 60 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software