KANG , Ross

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$. We investigate the ratio of the $k$-improper chromatic number to the clique number for unit disk graphs and random unit disk graphs to extend results of...

International audience

For any graph $G$, the $k$-improper chromatic number $\chi^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$. We investigate the ratio of the $k$-improper chromatic number to the clique number for unit disk graphs and random unit disk graphs to generalise...

Motivated by a satellite communications problem, we consider a generalised colouring problem on unit disk graphs. A colouring is k -improper if no vertex receives the same colour as k +1 of its neighbours. The k -improper chromatic number chi_k (G) is the least number of colours needed in a k -improper colouring of a graph G. The main sub ject...

In this paper, we study the notion of circular choosability recently introduced by Mohar and Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that, for every graph G, cch(G) = O( ch(G) + ln |V(G)| ). We investigate a generalisation of circular choosability, circular f-choosability, when f is a...

We study circular choosability, a notion recently introduced by Mohar and by Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that cch(G) = O(ch(G) + ln |V(G)|) for every graph G. We investigate a generalisation of circular choosability, the circular f-choosability, where f is a function of the...

In this paper, we study the notion of circular choosability recently introduced by Mohar and Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that, for every graph G, cch(G) = O( ch(G) + ln |V(G)| ). We investigate a generalisation of circular choosability, circular f-choosability, when f is a...