An upper bound for the chromatic number of line graphs
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 ho...
| Հիմնական հեղինակներ: | , , |
|---|---|
| Ձևաչափ: | Հոդված |
| Լեզու: | English |
| Հրապարակվել է: |
Discrete Mathematics & Theoretical Computer Science
2005-01-01
|
| Շարք: | Discrete Mathematics & Theoretical Computer Science |
| Խորագրեր: | |
| Առցանց հասանելիություն: | https://dmtcs.episciences.org/3401/pdf |