Academic Journal
Star Colourings of Subdivisions
| العنوان: | Star Colourings of Subdivisions |
|---|---|
| المؤلفون: | David R. Wood |
| المساهمون: | The Pennsylvania State University CiteSeerX Archives |
| المصدر: | http://neutron.scs.carleton.ca/research/tech_reports//2003/TR-03-02.pdf. |
| سنة النشر: | 2003 |
| المجموعة: | CiteSeerX |
| مصطلحات موضوعية: | graph colouring, star colouring, star chromatic number, subdivision |
| الوصف: | Let G be a graph with chromatic number χ(G) and maximum degree ∆(G). A star colouring of G is a function that assigns a colour to each vertex such that adja-cent vertices receive distinct colours, and there is no bichromatic 4-vertex path. The star chromatic number χst(G) is the minimum number of colours in a star colour-ing of G. Star colourings of subdivisions of graphs are investigated. Let G ′ be the graph obtained from G by subdividing each edge once. Bounds on χst(G′) in terms of χ(G) and ∆(G) are proved. In particular, χst(G′) ≤ max{χ(G), 3} and χst(G ′) ≤ √∆(G) + 3. Furthermore, if χst(G′) ≤ k then χ(G) ≤ k · 22k. Hence χst(G ′) is tied to χ(G). On the other hand, a graph H obtained from G by subdivid-ing each edge at least twice has χst(H) ≤ 4. |
| نوع الوثيقة: | text |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.573.1289; http://neutron.scs.carleton.ca/research/tech_reports//2003/TR-03-02.pdf |
| الاتاحة: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.573.1289 http://neutron.scs.carleton.ca/research/tech_reports//2003/TR-03-02.pdf |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| رقم الانضمام: | edsbas.AEAA2B05 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |