Results 1 to 10 of about 6,056 (148)
Improper colourings inspired by Hadwiger’s conjecture [PDF]
Journal of the London Mathematical Society, 2018 Hadwiger’s Conjecture asserts that every Kt-minor-free graph has a proper (t − 1)-colouring. We relax the conclusion in Hadwiger’s Conjecture via improper colourings.
DeVos M. +7 more
core +7 more sources
Acyclic improper colourings of graphs with bounded maximum degree [PDF]
Discrete Mathematics, 2010 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
Addario-Berry, Louigi +4 more
core +7 more sources
Improper colouring of (random) unit disk graphs [PDF]
Discrete Mathematics, 2005 For any graph $G$, the $k$-improper chromatic number $χ ^k(G)$ is the smallest number of colours used in a colouring of $G$ such that each colour class induces a subgraph of maximum degree $k$.
Jean-Sébastien Sereni +2 more
core +10 more sources
Improper colouring of weighted grid and hexagonal graphs [PDF]
, 2010 We study a weighted improper colouring problem on graph, and in particular of triangular and hexagonal grid graphs. This problem is motivated by a frequency allocation problem.
Bermond, Jean-Claude +3 more
core +4 more sources
Weighted Improper Colouring [PDF]
Journal of Discrete Algorithms, 2011 AbstractIn this paper, we study a colouring problem motivated by a practical frequency assignment problem and, up to our best knowledge, new. In wireless networks, a node interferes with other nodes, the level of interference depending on numerous parameters: distance between the nodes, geographical topography, obstacles, etc.
Araujo, Julio +5 more
openaire +6 more sources
On improper interval edge colourings [PDF]
Czechoslovak Mathematical Journal, 2016 We study improper interval edge colourings, defined by the requirement that the edge colours around each vertex form an integer interval. For the corresponding chromatic invariant (being the maximum number of colours in such a colouring), we present upper and lower bounds and discuss their qualities; also, we determine its values and estimates for ...
Hudák, Peter +3 more
openaire +3 more sources
On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 We consider non-trivial homomorphisms to reflexive oriented graphs in which some pair of adjacent vertices have the same image. Using a notion of convexity for oriented graphs, we study those oriented graphs that do not admit such homomorphisms. We fully classify those oriented graphs with tree-width $2$ that do not admit such homomorphisms and show ...
Christopher Duffy, Sonja Linghui Shan
openaire +6 more sources
On \delta^(k)-colouring of Powers of Paths and Cycles [PDF]
, 2021 In a proper vertex colouring of a graph, the vertices are coloured in such a way that no two adjacent vertices receive the same colour, whereas in an improper vertex colouring, adjacent vertices are permitted to receive same colours subjected to some ...
Ellumkalayil, Merlin Thomas, Ms +1 more
core +2 more sources
On monochromatic component size for improper colourings [PDF]
Discrete Applied Mathematics, 2005 AbstractThis paper concerns improper λ-colourings of graphs and focuses on the sizes of the monochromatic components (i.e., components of the subgraphs induced by the colour classes). Consider the following three simple operations, which should, heuristically, help reduce monochromatic component size: (a) assign to a vertex the colour that is least ...
Edwards, Keith, Farr, Graham
openaire +2 more sources
On parsimonious edge-colouring of graphs with maximum degree three [PDF]
, 2012 In a graph $G$ of maximum degree $\Delta$ let $\gamma$ denote the largest fraction of edges that can be $\Delta$ edge-coloured. Albertson and Haas showed that $\gamma \geq 13/15$ when $G$ is cubic . We show here that this result can be extended to graphs
Fouquet, Jean-Luc, Vanherpe, Jean-Marie
core +4 more sources