Geodesic
A strengthening of Brooks' Theorem for line graphs
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We prove that if $G$ is the line graph of a multigraph, then the chromatic number $\chi(G)$ of $G$ is at most $\max\left\{\omega(G), \frac{7\Delta(G) + 10}{8}\right\}$ where $\omega(G)$ and $\Delta(G)$ are the clique number and the maximum degree of $G$, respectively. Thus Brooks' Theorem holds for line graphs of multigraphs in much stronger form. Using similar methods we then prove that if $G$ is the line graph of a multigraph with $\chi(G) \geq \Delta(G) \geq 9$, then $G$ contains a clique on $\Delta(G)$ vertices. Thus the Borodin-Kostochka Conjecture holds for line graphs of multigraphs.
DOI : 10.37236/632
Classification : 05C15, 05C76 
@article{10_37236_632,
     author = {Landon Rabern},
     title = {A strengthening of {Brooks'} {Theorem} for line graphs},
     journal = {The electronic journal of combinatorics},
     year = {2011},
     volume = {18},
     number = {1},
     doi = {10.37236/632},
     zbl = {1225.05101},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/632/}
}
TY  - JOUR
AU  - Landon Rabern
TI  - A strengthening of Brooks' Theorem for line graphs
JO  - The electronic journal of combinatorics
PY  - 2011
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/632/
DO  - 10.37236/632
ID  - 10_37236_632
ER  - 
%0 Journal Article
%A Landon Rabern
%T A strengthening of Brooks' Theorem for line graphs
%J The electronic journal of combinatorics
%D 2011
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/632/
%R 10.37236/632
%F 10_37236_632
Landon Rabern. A strengthening of Brooks' Theorem for line graphs. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/632

Cité par Sources :