Geodesic
An upper bound for the chromatic number of line graphs
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

It was conjectured by Reed [reed98conjecture] that for any graph $G$, the graph's chromatic number $χ (G)$ is bounded above by $\lceil Δ (G) +1 + ω (G) / 2\rceil$ , where $Δ (G)$ and $ω (G)$ are the maximum degree and clique number of $G$, respectively. In this paper we prove that this bound holds if $G$ is the line graph of a multigraph. The proof yields a polynomial time algorithm that takes a line graph $G$ and produces a colouring that achieves our bound. 
@article{DMTCS_2005_special_250_a10,
     author = {King, Andrew D. and Reed, Bruce A. and Vetta, Adrian R.},
     title = {An upper bound for the chromatic number of line graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3401},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3401/}
}
TY  - JOUR
AU  - King, Andrew D.
AU  - Reed, Bruce A.
AU  - Vetta, Adrian R.
TI  - An upper bound for the chromatic number of line graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3401/
DO  - 10.46298/dmtcs.3401
LA  - en
ID  - DMTCS_2005_special_250_a10
ER  - 
%0 Journal Article
%A King, Andrew D.
%A Reed, Bruce A.
%A Vetta, Adrian R.
%T An upper bound for the chromatic number of line graphs
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3401/
%R 10.46298/dmtcs.3401
%G en
%F DMTCS_2005_special_250_a10
King, Andrew D.; Reed, Bruce A.; Vetta, Adrian R. An upper bound for the chromatic number of line graphs. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3401. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3401/

Cité par Sources :