Abstract | ||
---|---|---|
For graphs of bounded maximum degree, we consider acyclic t-improper colourings, that is, colourings in which each bipartite subgraph consisting of the edges between two colour classes is acyclic, and each colour class induces a graph with maximum degree at most t. We consider the supremum, over all graphs of maximum degree at most d, of the acyclic t-improper chromatic number and provide t-improper analogues of results by Alon, McDiarmid and Reed [N. Alon, C.J.H. McDiarmid, B. Reed, Acyclic coloring of graphs, Random Structures Algorithms 2 (3) (1991) 277-288] and Fertin, Raspaud and Reed [G. Fertin, A. Raspaud, B. Reed, Star coloring of graphs, J. Graph Theory 47 (3) (2004) 163-182]. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1016/j.disc.2008.09.009 | Discrete Mathematics |
Keywords | Field | DocType |
acyclic colouring,subcubic graphs,star colouring,improper colouring,bounded degree graphs,ch oosability,maximum degree | Discrete mathematics,Indifference graph,Combinatorics,Random graph,Bipartite graph,Star coloring,Star (graph theory),Degree (graph theory),Brooks' theorem,Mathematics,Acyclic coloring | Journal |
Volume | Issue | ISSN |
310 | 2 | Discrete Mathematics |
Citations | PageRank | References |
5 | 0.52 | 10 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Louigi Addario-Berry | 1 | 127 | 22.22 |
louis esperet | 2 | 148 | 24.86 |
Ross J. Kang | 3 | 86 | 18.12 |
Colin McDiarmid | 4 | 1071 | 167.05 |
Alexandre Pinlou | 5 | 167 | 20.47 |