Let $G$ be a simple graph such that some of its vertices are like a fork. i.e. there is vertices $w,x,a,v$ such that edges $[v,w]$ and $[w,a]$ are incident in $w$ and edges $[w,a]$ and $[x,w]$ are incident (and so adjacent) in $w$ but $[w,x]$ and $[v,w]$ are not adjacent. (see the following figure)

enter image description here

Question: Does this type of graphs have a name? What is the chromatic index(edge coloring number) of this type of graphs?

Motivation: Consider a Internet Bank service such that there is a server $w$ (bank) and users $v$ (customer) and $x$ (customer). Each user can access to own account in server, but no two user can access to each other.

  • 3
    $\begingroup$ I don't understand how there can be two vertices with the same name. There also seems to be a trivalent vertex that is not represented by a thick dot, just above the two $w$'s. Is the meaning of adjacent different to incident? Do you consider only planar graphs? Maybe you mean some of whose \textbf{edges} are like a fork? $\endgroup$ Dec 31 '17 at 19:44
  • $\begingroup$ All of graphs. The adjacent and incident are in it usual meaning. I don't understand "There also a trivalent vertex that is not represented." can be there or there is in picture? $\endgroup$
    – C.F.G
    Dec 31 '17 at 19:51
  • 1
    $\begingroup$ A "usual" graph can be equivalently given by the set of flags, together with an equivalence relation (its equivalence classes being vertices) and a free involution (its orbits being edges). If you want something unusual like in this question, you can start with this and then replace equivalence relation with a cover and involutions with something more weird $\endgroup$ Dec 31 '17 at 20:52
  • $\begingroup$ In my dictionary the "usual meaning" of "adjacent" is this: Two (distinct) edges are adjacent if they share a common vertex. So if $x\not=v$, then the two edge $[x,w]$ and $[v,w]$ are adjacent, since they share the vertex $w$. $\endgroup$
    – Goldstern
    Dec 31 '17 at 22:13
  • $\begingroup$ In fact for this particular feature you may leave edges undisturbed (i. e. they will be orbits of a free involution on flags). It is that vertices will be now possibly intersecting elements of a cover of the set of flags. For your picture, the flags will be $x_a,x_w,w_x,w_a,w_v,a_x,a_w,a_v,v_a,v_w,...$, with the involution interchanging each pair $(p_q,q_p)$, and vertices will be $\{x_a,x_w,...\}$, $\{w_a,w_x\}$, $\{w_a,w_v\}$, $\{a_x,a_w,a_v\}$, $\{v_w,v_a,...\}$, ... $\endgroup$ Dec 31 '17 at 23:09

Define a multiflag graph to be a triple $G=(F,\mathscr V,\tau)$ consisting of some set $F$, called the set of flags of $G$; some subset $\mathscr V\subseteq\mathscr PF$ of the powerset of $F$, called the set of vertices of $G$, and a free involution $\tau:F\to F$ on flags. Here, $\mathscr V$ is required to be a cover of $F$, that is, $\bigcup\mathscr V=F$.

Every "ordinary" undirected graph $(V,E)$ gives rise to such a structure, with $F$ the incidence relation of the graph, that is, the set of pairs $(v,e)$ where $e\in E$ is an edge and $v\in V$ is a vertex of $e$. Here $\mathscr V$ consists of the sets $F_v:=\{(v,e)\mid\text{$v$ is a vertex of $e$}\}$, one for each $v\in V$ (since $F_v\ne F_{v'}$ for $v\ne v'$, one might identify $V$ with $\mathscr V$). Moreover $\tau(v,e)=(v',e)$ where $v'$ is the (unique) vertex of $e$ different from $v$.

It is well known that in this way one obtains a one-to-one correspondence between undirected graphs and those multiflag graphs for which $\mathscr V$ is not only a cover but also a partition of $F$, i.e. satisfies $F_1\cap F_2=\varnothing$ for $F_1\ne F_2$, $F_1,F_2\in\mathscr V$. In this case to each element of $F$ corresponds a unique element of $\mathscr V$ (the one containing it), and one usually pictures flags as "half-edges" $\bullet\!-$, with $\tau$ interchanging two half-edges forming an edge (like ${\bullet\!-}{-\!\bullet}$).

If one drops this additional restriction one can include examples like yours: for

enter image description here

we would have


$\mathscr V=\{\{p_x,p_q\},\{q_p,q_v\},\{v_q,v_a,v_w\},\{w_v,w_a\},\{w_x,w_a\},\{x_w,x_a,x_p\}\}$


$\tau(i_j)=j_i$ for all $i_j\in F$.

This does not give rise to an ordinary graph since $\{w_v,w_a\}\cap\{w_x,w_a\}\ne\varnothing$; one can say that the flag $w_a$ is "two-headed", i. e. describes a "half-edge" with two "heads".

  • $\begingroup$ Thanks. but what is the chromatic index of this type of graphs (multiflag graphs)? $\endgroup$
    – C.F.G
    Jan 2 '18 at 12:34
  • $\begingroup$ You can extend the definition of chromatic index in various ways. Which one is suitable for you depends on how are you going to use it. One possible definition is to call edges $(i_j,j_i)$ and $(k_l,l_k)$ adjacent if there is an element of $\mathscr V$ containing either both $i_j$ and $k_l$, or both $i_j$ and $l_k$, or both $j_i$ and $k_l$, or both $j_i$ and $l_k$. Another (nonequivalent) definition would be to call them adjacent if either $i=k$ or $i=l$ or $j=k$ or $j=l$. There might be other possibilities too. After you have chosen definition of adjacency, chromatic index is defined as usual $\endgroup$ Jan 2 '18 at 18:46

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.