<p>I don't know if this problem has another name, but it seems like it's easy to solve.</p>
<p>We first see that a weak incidence coloring of a graph <span class="math-container">$G$</span> corresponds to an edge coloring of the graph <span class="math-container">$G'$</span> obtained by subdividing each edge of <span class="math-container">$G$</span> once. This, in turn, corresponds to a vertex coloring of <span class="math-container">$L(G')$</span>, the line graph of <span class="math-container">$G'$</span>. This line graph consists of a collection of cliques, one for each vertex in the original graph <span class="math-container">$G$</span>. Each vertex in each clique is adjacent to one and only one vertex in another clique.</p>
<p>Now, it is not hard to prove that <span class="math-container">$L(G')$</span> is a perfect graph by the strong perfect graph theorem (neither <span class="math-container">$L(G')$</span> or <span class="math-container">$\overline{L(G')}$</span> have any long odd cycles). This implies that the chromatic number of <span class="math-container">$L(G')$</span> is equal to the size of the largest clique in <span class="math-container">$L(G')$</span>, which in turn implies that the weak incidence coloring number of <span class="math-container">$G$</span> is equal to <span class="math-container">$\Delta(G)$</span>.</p>

CC BY-SA 4.0
2021-04-04T10:17:27.110Z
2021-04-04T10:17:27.110Z
Highheath
<p>Let <span class="math-container">$G(V,E)$</span> be a simple undirected graph, let <span class="math-container">$k\in \mathbb{N}$</span>, and let <span class="math-container">$I(G)=\{(v,e)\ :\ e\in E, v\in e \}$</span> (here, <span class="math-container">$v\in e$</span> means <span class="math-container">$v$</span> is incident on <span class="math-container">$e$</span>). A <span class="math-container">$k$</span>-incidence colouring of <span class="math-container">$G$</span> is a function <span class="math-container">$c:I(G)\to \{1,2,\dots,k\}$</span> such that the following hold for all <span class="math-container">$u,v\in V$</span> and <span class="math-container">$e,f\in E$</span> :<br />
(i) <span class="math-container">$c(\,(v,e)\,)\neq c(\,(v,f)\,)$</span>,<br />
(ii) <span class="math-container">$c(\,(u,e)\,)\neq c(\,(v,e)\,)$</span>, and<br />
(iii) if <span class="math-container">$e=\{u,v\}$</span>, then <span class="math-container">$c(\,(u,e)\,)\neq c(\,(v,f)\,)$</span>.</p>
<p>I am interested in the weak variant where we drop condition (iii). Let us call it weak incidence colouring. That is, a <span class="math-container">$k$</span>-weak incidence colouring of <span class="math-container">$G$</span> is a function <span class="math-container">$c:I(G)\to \{1,2,\dots,k\}$</span> such that <span class="math-container">$c(\,(v,e)\,)\neq c(\,(v,f)\,)$</span>,  and <span class="math-container">$c(\,(u,e)\,)\neq c(\,(v,e)\,)$</span> for all <span class="math-container">$u,v\in V$</span> and <span class="math-container">$e,f\in E$</span>. This seems to be a very natural relaxation to me.<br />
<strong>I couldn't find any paper that study weak incidence colouring.<br />
Is this because this is equivalent to some known notion?</strong><br />
We know that incidence colouring has several equivalent characterizations, for instance, in terms of strong edge colouring (or directed star arboricity). See &quot;Links with other notions&quot; in <a href="https://www.labri.fr/perso/sopena/pmwiki/index.php?n=TheIncidenceColoringPage.TheIncidenceColoringPage" rel="nofollow noreferrer">The Incidence Coloring Page</a> maintained by Éric Sopena.</p>
<p>If it matters, I am particularly interested in the complexity of <span class="math-container">$k$</span>-weak incidence colouring of <span class="math-container">$k$</span>-regular graphs. Thank you, in advance.</p>

<graph-theory><graph-colouring>
Weak incidence colouring
Cyriac Antony
# Weak incidence colouring

(Asked by: username_0 on 2021-04-03)

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](https://www.labri.fr/perso/sopena/pmwiki/index.php?n=TheIncidenceColoringPage.TheIncidenceColoringPage) 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.

**Tags:** graph-theory, graph-colouring


---

## 1 answers

### Answer by username_1 on 2021-04-04. Score: 2 | Accepted answer

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)$.


---

