Let $G(V,E)$ be a simple undirected graph, let $k\in \mathbb{N}$, and let $I(G)=\{(v,e)\ :\ e\in E, v\in e \}$ (here, $v\in e$ means $v$ is incident on $e$). A $k$-incidence colouring of $G$ is a function $c:I(G)\to \{1,2,\dots,k\}$ such that the following hold for all $u,v\in V$ and $e,f\in E$ :
(i) $c(\,(v,e)\,)\neq c(\,(v,f)\,)$,
(ii) $c(\,(u,e)\,)\neq c(\,(v,e)\,)$, and
(iii) if $e=\{u,v\}$, then $c(\,(u,e)\,)\neq c(\,(v,f)\,)$.

I am interested in the weak variant where we drop condition (iii). Let us call it weak incidence colouring. That is, a $k$-weak incidence colouring of $G$ is a function $c:I(G)\to \{1,2,\dots,k\}$ such that $c(\,(v,e)\,)\neq c(\,(v,f)\,)$, and $c(\,(u,e)\,)\neq c(\,(v,e)\,)$ for all $u,v\in V$ and $e,f\in E$. This seems to be a very natural relaxation to me.
I couldn't find any paper that study weak incidence colouring.
Is this because this is equivalent to some known notion?

We know that incidence colouring has several equivalent characterizations, for instance, in terms of strong edge colouring (or directed star arboricity). See "Links with other notions" in The Incidence Coloring Page maintained by Éric Sopena.

If it matters, I am particularly interested in the complexity of $k$-weak incidence colouring of $k$-regular graphs. Thank you, in advance.


I don't know if this problem has another name, but it seems like it's easy to solve.

We first see that a weak incidence coloring of a graph $G$ corresponds to an edge coloring of the graph $G'$ obtained by subdividing each edge of $G$ once. This, in turn, corresponds to a vertex coloring of $L(G')$, the line graph of $G'$. This line graph consists of a collection of cliques, one for each vertex in the original graph $G$. Each vertex in each clique is adjacent to one and only one vertex in another clique.

Now, it is not hard to prove that $L(G')$ is a perfect graph by the strong perfect graph theorem (neither $L(G')$ or $\overline{L(G')}$ have any long odd cycles). This implies that the chromatic number of $L(G')$ is equal to the size of the largest clique in $L(G')$, which in turn implies that the weak incidence coloring number of $G$ is equal to $\Delta(G)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.