Acyclic, Star and Oriented Colourings of Graph Subdivisions
Let G be a graph with chromatic number χ (G). A vertex colouring of G is \emphacyclic if each bichromatic subgraph is a forest. A \emphstar colouring of G is an acyclic colouring in which each bichromatic subgraph is a star forest. Let χ _a(G) and χ _s(G) denote the acyclic and star chromatic number...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2005-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/344/pdf |
| _version_ | 1827323884310888448 |
|---|---|
| author | David R. Wood |
| author_facet | David R. Wood |
| author_sort | David R. Wood |
| collection | DOAJ |
| description | Let G be a graph with chromatic number χ (G). A vertex colouring of G is \emphacyclic if each bichromatic subgraph is a forest. A \emphstar colouring of G is an acyclic colouring in which each bichromatic subgraph is a star forest. Let χ _a(G) and χ _s(G) denote the acyclic and star chromatic numbers of G. This paper investigates acyclic and star colourings of subdivisions. Let G' be the graph obtained from G by subdividing each edge once. We prove that acyclic (respectively, star) colourings of G' correspond to vertex partitions of G in which each subgraph has small arboricity (chromatic index). It follows that χ _a(G'), χ _s(G') and χ (G) are tied, in the sense that each is bounded by a function of the other. Moreover the binding functions that we establish are all tight. The \emphoriented chromatic number χ ^→(G) of an (undirected) graph G is the maximum, taken over all orientations D of G, of the minimum number of colours in a vertex colouring of D such that between any two colour classes, all edges have the same direction. We prove that χ ^→(G')=χ (G) whenever χ (G)≥ 9. |
| first_indexed | 2024-04-25T01:59:48Z |
| format | Article |
| id | doaj.art-a1d53c5cdb3f43299196b98316f50b64 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:59:48Z |
| publishDate | 2005-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-a1d53c5cdb3f43299196b98316f50b642024-03-07T15:07:34ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502005-01-01Vol. 710.46298/dmtcs.344344Acyclic, Star and Oriented Colourings of Graph SubdivisionsDavid R. Wood0https://orcid.org/0000-0001-8866-3041Departament de Matemàtica Aplicada IILet G be a graph with chromatic number χ (G). A vertex colouring of G is \emphacyclic if each bichromatic subgraph is a forest. A \emphstar colouring of G is an acyclic colouring in which each bichromatic subgraph is a star forest. Let χ _a(G) and χ _s(G) denote the acyclic and star chromatic numbers of G. This paper investigates acyclic and star colourings of subdivisions. Let G' be the graph obtained from G by subdividing each edge once. We prove that acyclic (respectively, star) colourings of G' correspond to vertex partitions of G in which each subgraph has small arboricity (chromatic index). It follows that χ _a(G'), χ _s(G') and χ (G) are tied, in the sense that each is bounded by a function of the other. Moreover the binding functions that we establish are all tight. The \emphoriented chromatic number χ ^→(G) of an (undirected) graph G is the maximum, taken over all orientations D of G, of the minimum number of colours in a vertex colouring of D such that between any two colour classes, all edges have the same direction. We prove that χ ^→(G')=χ (G) whenever χ (G)≥ 9.https://dmtcs.episciences.org/344/pdfsubdivisionoriented chromatic numberoriented colouringgraphgraph colouringstar colouringstar chromatic numberacyclic colouringacyclic chromatic number[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | David R. Wood Acyclic, Star and Oriented Colourings of Graph Subdivisions Discrete Mathematics & Theoretical Computer Science subdivision oriented chromatic number oriented colouring graph graph colouring star colouring star chromatic number acyclic colouring acyclic chromatic number [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | Acyclic, Star and Oriented Colourings of Graph Subdivisions |
| title_full | Acyclic, Star and Oriented Colourings of Graph Subdivisions |
| title_fullStr | Acyclic, Star and Oriented Colourings of Graph Subdivisions |
| title_full_unstemmed | Acyclic, Star and Oriented Colourings of Graph Subdivisions |
| title_short | Acyclic, Star and Oriented Colourings of Graph Subdivisions |
| title_sort | acyclic star and oriented colourings of graph subdivisions |
| topic | subdivision oriented chromatic number oriented colouring graph graph colouring star colouring star chromatic number acyclic colouring acyclic chromatic number [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/344/pdf |
| work_keys_str_mv | AT davidrwood acyclicstarandorientedcolouringsofgraphsubdivisions |