Name
Abstract | ||
|---|---|---|
Brualdi and Quinn Massey [6] defined incidence colouring while studying the strong edge chromatic index of bipartite graphs. Here we introduce a similar concept for digraphs and define the oriented incidence chromatic number. Using digraph homomorphisms, we show that the oriented incidence chromatic number of a digraph is closely related to the chromatic number of the underlying simple graph. This motivates our study of the oriented incidence chromatic number of symmetric complete digraphs. We give upper and lower bounds for the oriented incidence chromatic number of these graphs, as well as digraphs arising from common graph constructions and decompositions. Additionally we construct, for all k >= 2, a target digraph H-k for which oriented incidence k colouring is equivalent to homomorphism to H-k. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.7151/dmgt.2076 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
digraph homomorpism,graph colouring,incidence colouring,computational complexity | Discrete mathematics,Combinatorics,Graph colouring,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
39 | 1 | 1234-3099 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christopher Duffy | 1 | 1 | 2.10 |
| Gary MacGillivray | 2 | 344 | 43.25 |
| Pascal Ochem | 3 | 258 | 36.91 |
| André Raspaud | 4 | 850 | 85.91 |