Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Acyclic, Star and Or ...
Article

Acyclic, Star and Oriented Colourings of Graph Subdivisions

David R. Wood ORCID (1)
(1) Departament de Matemàtica Aplicada II
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2005
Last modified on
March 31, 2025
Volume 7
vol. 7
DOI
10.46298/dmtcs.344
License
https://about.hal.science/hal-authorisation-v1
Indicators
1209
Views
1753
Downloads

Acyclic, Star and Oriented Colourings of Graph Subdivisions

David R. Wood ORCID (1)
(1) Departament de Matemàtica Aplicada II
Abstract
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • graph
  • graph colouring
  • star colouring
  • star chromatic number
  • acyclic colouring
  • acyclic chromatic number
  • oriented colouring
  • oriented chromatic number
  • subdivision
Cited by

Source: OpenCitations

  • Strong Oriented Chromatic Number of Planar Graphs without Short Cycles

    Discrete Mathematics & Theoretical Computer Science

    Authors : Mickael Montassier, Pascal Ochem ORCID, Alexandre Pinlou ORCID

    Journal reference : Volume Vol. 10 no. 1, 2008, pp.

    DOI : 10.46298/dmtcs.418

  • Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours

    The Electronic Journal of Combinatorics

    Authors : Vida Dujmović ORCID, Gwenaël Joret ORCID, Fabrizio Frati ORCID, David R. Wood ORCID

    Journal reference : Volume 20, 2013, pp.

    DOI : 10.37236/3153

  • Acyclic colorings of graph subdivisions revisited

    Journal of Discrete Algorithms

    Authors : Debajyoti Mondal ORCID, Rahnuma Islam Nishat ORCID, Sue Whitesides, Md. Saidur Rahman ORCID

    Journal reference : Volume 16, 2012, pp. 90-103

    DOI : 10.1016/j.jda.2012.06.001

  • Obstructions to Injective Oriented Colourings

    Electronic Notes in Discrete Mathematics

    Authors : Gary MacGillivray ORCID, André Raspaud, Jacobus Swarts

    Journal reference : Volume 38, 2011, pp. 597-605

    DOI : 10.1016/j.endm.2011.10.001

  • Q -Ramsey classes of graphs

    Discrete Mathematics

    Authors : Mieczysław Borowiecki ORCID, Anna Fiedorowicz ORCID

    Journal reference : Volume 312, 2012, pp. 3437-3443

    DOI : 10.1016/j.disc.2012.02.007

  • Oriented vertex and arc colorings of outerplanar graphs

    Information Processing Letters

    Authors : Alexandre Pinlou ORCID, Éric Sopena ORCID

    Journal reference : Volume 100, 2006, pp. 97-104

    DOI : 10.1016/j.ipl.2006.06.012

  • On forbidden subdivision characterizations of graph classes

    European Journal of Combinatorics

    Authors : Zdeněk Dvořák ORCID

    Journal reference : Volume 29, 2007, pp. 1321-1332

    DOI : 10.1016/j.ejc.2007.05.008

  • Acyclic Colorings of Graphs with Obstructions

    SIAM Journal on Discrete Mathematics

    Authors : Quentin Chuet, Johanne Cohen ORCID, François Pirot ORCID

    Journal reference : Volume 39, 2025, pp. 505-532

    DOI : 10.1137/23m1556162

  • Acyclic, star and injective colouring: A complexity picture for H-free graphs

    Journal of Computer and System Sciences

    Authors : Jan Bok ORCID, Nikola Jedličková ORCID, Barnaby Martin ORCID, Pascal Ochem ORCID, Daniël Paulusma ORCID, Siani Smith ORCID

    Journal reference : Volume 154, 2025, pp. 103662

    DOI : 10.1016/j.jcss.2025.103662

  • The oriented chromatic number of the hexagonal grid is 6

    Discrete Applied Mathematics

    Authors : Antoni Lozano ORCID

    Journal reference : Volume 355, 2024, pp. 122-128

    DOI : 10.1016/j.dam.2024.04.032

  • On the oriented chromatic index of oriented graphs

    Journal of Graph Theory

    Authors : Pascal Ochem ORCID, Alexandre Pinlou ORCID, Éric Sopena ORCID

    Journal reference : Volume 57, 2007, pp. 313-332

    DOI : 10.1002/jgt.20286

  • Star chromatic bounds

    Electronic Notes in Discrete Mathematics

    Authors : T. Karthick

    Journal reference : Volume 53, 2016, pp. 413-419

    DOI : 10.1016/j.endm.2016.05.035

  • Acyclic coloring with few division vertices

    Journal of Discrete Algorithms

    Authors : Debajyoti Mondal ORCID, Rahnuma Islam Nishat ORCID, Md. Saidur Rahman ORCID, Sue Whitesides

    Journal reference : Volume 23, 2013, pp. 42-53

    DOI : 10.1016/j.jda.2013.08.002

  • Oriented colouring graphs of bounded degree and degeneracy

    Discrete Mathematics

    Authors : A. Clow ORCID, L. Stacho

    Journal reference : Volume 349, 2025, pp. 114746

    DOI : 10.1016/j.disc.2025.114746

  • On the r-dynamic coloring of the direct product of a path and a k-subdivision of a star graph

    Discrete Mathematics Algorithms and Applications

    Authors : Raúl M. Falcón ORCID, M. Venkatachalam, S. Gowri, G. Nandini

    Journal reference : Volume 14, 2021, pp.

    DOI : 10.1142/s1793830921501214

  • On Oriented Arc-Coloring of Subcubic Graphs

    The Electronic Journal of Combinatorics

    Authors : Alexandre Pinlou ORCID

    Journal reference : Volume 13, 2006, pp.

    DOI : 10.37236/1095

  • Spectra, Hitting Times and Resistance Distances ofq- Subdivision Graphs

    arXiv (Cornell University)

    Authors : Yibo Zeng, Zhongzhi Zhang ORCID

    Journal reference : Volume 64, 2019, pp. 76-92

    DOI : 10.1093/comjnl/bxz141

  • From χ- to χ-bounded classes

    Authors : Yiting Jiang ORCID, Jaroslav Nešetřil ORCID, Patrice Ossona de Mendez ORCID

    Journal reference : Volume 158, 2021, pp. 186-209

    DOI : 10.1016/j.jctb.2021.05.006

  • On star and acyclic coloring of generalized lexicographic product of graphs

    AIMS Mathematics

    Authors : Jin Cai, Shuangliang Tian, Lizhen Peng

    Journal reference : Volume 7, 2022, pp. 14270-14281

    DOI : 10.3934/math.2022786

  • Degrees in Oriented Hypergraphs and Ramsey p-Chromatic Number

    The Electronic Journal of Combinatorics

    Authors : Yair Caro ORCID, Adriana Hansberg ORCID

    Journal reference : Volume 19, 2012, pp.

    DOI : 10.37236/2576

  • On the oriented chromatic number of dense graphs

    Libraries and Cultural Resources (University of Calgary)

    Authors : Wood

    Journal reference : Volume 2, 2007, pp. 145-152

    DOI : 10.11575/cdm.v2i2.61971

  • Nonrepetitive colouring via entropy compression

    arXiv (Cornell University)

    Authors : Vida Dujmović ORCID, Gwenaël Joret ORCID, Jakub Kozik ORCID, David R. Wood ORCID

    Journal reference : Volume 36, 2015, pp. 661-686

    DOI : 10.1007/s00493-015-3070-6

  • Obstructions to locally injective oriented improper colourings

    European Journal of Combinatorics

    Authors : Gary MacGillivray ORCID, André Raspaud, Jacobus Swarts

    Journal reference : Volume 35, 2013, pp. 402-412

    DOI : 10.1016/j.ejc.2013.06.023

  • Homomorphisms and colourings of oriented graphs: An updated survey

    Discrete Mathematics

    Authors : É. Sopena ORCID

    Journal reference : Volume 339, 2015, pp. 1993-2005

    DOI : 10.1016/j.disc.2015.03.018

  • Oriented Coloring: Complexity and Approximation

    Lecture notes in computer science

    Authors : Jean-François Culus, Marc Demange ORCID

    Journal reference : Volume , 2006, pp. 226-236

    DOI : 10.1007/11611257_20

  • On acyclic colorings of graphs

    2012 15th International Conference on Computer and Information Technology (ICCIT)

    Authors : Abu Reyan Ahmed, Md. Mazharul Islam ORCID, Md. Saidur Rahman ORCID

    Journal reference : Volume , 2012, pp. 95-100

    DOI : 10.1109/iccitechn.2012.6509751

  • Star coloring of cubic graphs

    Information Processing Letters

    Authors : Dezheng Xie, Huanhuan Xiao, Zhihong Zhao ORCID

    Journal reference : Volume 114, 2014, pp. 689-691

    DOI : 10.1016/j.ipl.2014.05.013
Preview
Loading PDF preview...