#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\use_default_options true
\begin_modules
algorithm2e
\end_modules
\maintain_unincluded_children false
\language spanish
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style french
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Standard
Dado un grafo 
\begin_inset Formula $G=(V,E)$
\end_inset

 y un conjunto 
\begin_inset Formula $S$
\end_inset

 de 
\series bold
colores
\series default
, llamamos 
\series bold
coloración
\series default
 (
\series bold
propia por vértices
\series default
) de 
\begin_inset Formula $G$
\end_inset

 a una función 
\begin_inset Formula $f:V\to S$
\end_inset

 con 
\begin_inset Formula $f(u)\neq f(v)$
\end_inset

 para 
\begin_inset Formula $(u,v)\in E$
\end_inset

.
 Si 
\begin_inset Formula $|S|=k$
\end_inset

, 
\begin_inset Formula $f$
\end_inset

 es una 
\series bold

\begin_inset Formula $k$
\end_inset

-coloración
\series default
, y 
\begin_inset Formula $G$
\end_inset

 es 
\series bold

\begin_inset Formula $k$
\end_inset

-coloreable
\series default
 si admite una 
\begin_inset Formula $k$
\end_inset

-coloración.
 Una 
\begin_inset Formula $k$
\end_inset

-coloración 
\begin_inset Formula $f$
\end_inset

 induce una partición de 
\begin_inset Formula $V$
\end_inset

 en subconjuntos independientes, dados por 
\begin_inset Formula $f^{-1}(c)$
\end_inset

 para 
\begin_inset Formula $c\in S$
\end_inset

.
\end_layout

\begin_layout Standard
El 
\series bold
número cromático
\series default
 de un grafo 
\begin_inset Formula $G$
\end_inset

, 
\begin_inset Formula $\chi(G)$
\end_inset

, es el menor 
\begin_inset Formula $k$
\end_inset

 tal que 
\begin_inset Formula $G$
\end_inset

 es 
\begin_inset Formula $k$
\end_inset

-coloreable.
 Ejemplos:
\end_layout

\begin_layout Enumerate
\begin_inset Formula $\chi(K_{n})=n$
\end_inset

.
\end_layout

\begin_deeper
\begin_layout Standard
En adelante el grafo a considerar será 
\begin_inset Formula $(V,E)$
\end_inset

 y 
\begin_inset Formula $f$
\end_inset

 será una coloración.
 Entonces, en este caso, 
\begin_inset Formula $f(i)\neq f(j)$
\end_inset

 para 
\begin_inset Formula $i\neq j$
\end_inset

, luego 
\begin_inset Formula $f$
\end_inset

 es inyectiva y su imagen tiene cardinal 
\begin_inset Formula $|V|=n$
\end_inset

.
\end_layout

\end_deeper
\begin_layout Enumerate
\begin_inset Formula $\chi(G)=0$
\end_inset

 si y sólo si 
\begin_inset Formula $G$
\end_inset

 es vacío.
\end_layout

\begin_deeper
\begin_layout Enumerate
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\implies$
\end_inset


\end_layout

\end_inset

Si 
\begin_inset Formula $\chi(G)=0$
\end_inset

, en particular existe 
\begin_inset Formula $f:V\to\emptyset$
\end_inset

 y 
\begin_inset Formula $V=\emptyset$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\impliedby]$
\end_inset


\end_layout

\end_inset

Si 
\begin_inset Formula $V=\emptyset$
\end_inset

, 
\begin_inset Formula $E=\emptyset$
\end_inset

 y 
\begin_inset Formula $f:V\to\emptyset$
\end_inset

 es una 0-coloración.
\end_layout

\end_deeper
\begin_layout Enumerate
\begin_inset Formula $\chi(G)=1$
\end_inset

 si y sólo si 
\begin_inset Formula $G$
\end_inset

 es no vacío y sin ejes.
\end_layout

\begin_deeper
\begin_layout Enumerate
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\implies]$
\end_inset


\end_layout

\end_inset

Si existiera 
\begin_inset Formula $(u,v)\in E$
\end_inset

 sería 
\begin_inset Formula $f(u)\neq f(v)$
\end_inset

 y por tanto 
\begin_inset Formula $|f(V)|\geq2\#$
\end_inset

, y si fuera 
\begin_inset Formula $V=\emptyset$
\end_inset

 sería 
\begin_inset Formula $|f(V)|=0\#$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\impliedby]$
\end_inset


\end_layout

\end_inset

Claramente 
\begin_inset Formula $|f(V)|\geq1$
\end_inset

, pero podemos tomar todos los nodos del mismo color.
\end_layout

\end_deeper
\begin_layout Enumerate
\begin_inset Formula $\chi(G)=2$
\end_inset

 si y sólo si 
\begin_inset Formula $G$
\end_inset

 es bipartito con algún eje.
\end_layout

\begin_deeper
\begin_layout Enumerate
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\implies]$
\end_inset


\end_layout

\end_inset

La partición 
\begin_inset Formula $\{f^{-1}(0),f^{-1}(1)\}$
\end_inset

 de 
\begin_inset Formula $V$
\end_inset

 cumple que eje une dos vértices en el mismo conjunto y por tanto todos
 unen un vértice de uno con uno del otro.
 Hay algún eje porque si no lo hubiera sería 
\begin_inset Formula $\chi(G)=1$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Argument item:1
status open

\begin_layout Plain Layout
\begin_inset Formula $\impliedby]$
\end_inset


\end_layout

\end_inset

Sea 
\begin_inset Formula $(A,B)$
\end_inset

 la partición, definimos 
\begin_inset Formula $f(v):=0$
\end_inset

 para 
\begin_inset Formula $v\in A$
\end_inset

 y 
\begin_inset Formula $f(v):=1$
\end_inset

 para 
\begin_inset Formula $v\in B$
\end_inset

.
 Entonces 
\begin_inset Formula $f$
\end_inset

 es una 2-coloración de 
\begin_inset Formula $G$
\end_inset

, y como hay algún eje, 
\begin_inset Formula $\chi(G)>1$
\end_inset

.
\end_layout

\end_deeper
\begin_layout Enumerate
Todo árbol no trivial es bipartito.
\end_layout

\begin_deeper
\begin_layout Standard
Se tiene 
\begin_inset Formula $|V|\geq2$
\end_inset

 y, sea 
\begin_inset Formula $n(v)$
\end_inset

 el nivel de un 
\begin_inset Formula $v\in V$
\end_inset

, 
\begin_inset Formula $f:V\to\{0,1\}$
\end_inset

 dada por 
\begin_inset Formula $f(v):=[n(v)]_{2}$
\end_inset

 es una coloración de 
\begin_inset Formula $G$
\end_inset

.
 Como 
\begin_inset Formula $G$
\end_inset

 tiene ejes, 
\begin_inset Formula $\chi(G)>1$
\end_inset

 y 
\begin_inset Formula $\chi(G)=2$
\end_inset

.
\end_layout

\end_deeper
\begin_layout Enumerate
Sea 
\begin_inset Note Note
status open

\begin_layout Plain Layout

\end_layout

\end_inset


\begin_inset Formula $C_{n}:=(\{1,\dots,n\},\{\{$
\end_inset


\end_layout

\end_body
\end_document