Matematické Fórum

byk7 · 19. 02. 2014 12:21

Zdravím,
existuje nějaký odhad zdola chromatického čísla pomocí $n$ vrcholů a $m$ hran?

reimu · 19. 02. 2014 15:26

Nevím o žádném vztahu, ve kterém by tyto hodnoty přímo vystupovaly. MathOverflow nabízí jisté metody, ale sotva dostatečně obecné.

byk7 · 19. 02. 2014 18:25

Díky, škoda... Je zajímavé, že takový horní odhad ale existuje.

JohnPeca18 · 19. 02. 2014 22:33

No určite existuje odhad pomocou m a n, kolko maximalne hran moze mat graf o n vrcholoch aby neobsahoval uplny graf o r vrcholoch. Su to takzvane Turanove grafy. Potom existuje aj vztah

$\lim_{n\to\infty} ex(n,H)\binom{n}{2}^{-1}=\frac{\chi(H)-2}{\chi(H)-1}$

kde ex(n,H) je prave pocet hran ktore moze mat graf na n vrcholoch bez toho aby obsahoval podgraf H.
Ked tak si skus viac pozriet Diestela, kapitolu 7, extremal graph theory

http://diestel-graph-theory.com/basic.html

byk7 · 20. 02. 2014 00:16

↑ JohnPeca18:

Díky, spíš mě zaujalo to v tom odkazu od ↑ reimu:.
Tam se píše, že

Hoffman's bound states that $\chi(G)\ge1-\frac{\lambda_1(G)}{\lambda_n(G)}$ where $\lambda_1(G), \lambda_n(G)$ denote the largest and smallest eigenvalues of the adjacency matrix of $G$ . (Note that $\lambda_n(G)$ is negative.)

Matematické Fórum

#1 19. 02. 2014 12:21

Dolní odhad chromatického čísla grafu

#2 19. 02. 2014 15:26

Re: Dolní odhad chromatického čísla grafu

#3 19. 02. 2014 18:25

Re: Dolní odhad chromatického čísla grafu

#4 19. 02. 2014 22:33

Re: Dolní odhad chromatického čísla grafu

#5 20. 02. 2014 00:16

Re: Dolní odhad chromatického čísla grafu

Zápatí