![](/files/happy5.png)
Iradmusa, Moharram
Vertex Coloring of graph fractional powers ★★★
Author(s): Iradmusa
Conjecture Let
be a graph and
be a positive integer. The
power of
, denoted by
, is defined on the vertex set
, by connecting any two distinct vertices
and
with distance at most
. In other words,
. Also
subdivision of
, denoted by
, is constructed by replacing each edge
of
with a path of length
. Note that for
, we have
.
Now we can define the fractional power of a graph as follows:
Let
be a graph and
. The graph
is defined by the
power of the
subdivision of
. In other words
.
Conjecture. Let
be a connected graph with
and
be a positive integer greater than 1. Then for any positive integer
, we have
.
In [1], it was shown that this conjecture is true in some special cases.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ k- $](/files/tex/43b5fd302d8f5ba143bb34369c40636c5feeb788.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G^k $](/files/tex/b048ddc696cdd8a621b159501fa5695e3fae99e8.png)
![$ V(G) $](/files/tex/b324b54d8674fa66eb7e616b03c7a601ccdab6b8.png)
![$ x $](/files/tex/e7ba5befcaa0d78e43b5176d70ce67425fd0fcdc.png)
![$ y $](/files/tex/739107c42bdb8452402d548efae98c3ce282847d.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ E(G^k)=\{xy:1\leq d_G(x,y)\leq k\} $](/files/tex/cd8a338d99bc211240133418299a99f45d85566d.png)
![$ k- $](/files/tex/43b5fd302d8f5ba143bb34369c40636c5feeb788.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G^\frac{1}{k} $](/files/tex/45627e469c3e3143a2f1499679bea01b7013d482.png)
![$ ij $](/files/tex/9530dc3006b9c8470f5e528b0d01c0cc9b574745.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ k=1 $](/files/tex/ca53a4ec21e82327d0698fdf47e1dcf798650081.png)
![$ G^\frac{1}{1}=G^1=G $](/files/tex/96c53e9d5e60fa2c160cb3b11ebb735aaee99b5b.png)
Now we can define the fractional power of a graph as follows:
Let
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ m,n\in \mathbb{N} $](/files/tex/2d562ef5fbde200560d931d849894c9df0513426.png)
![$ G^{\frac{m}{n}} $](/files/tex/b971ba9ba6139f14f028cf60a78690e72c2c8b40.png)
![$ m- $](/files/tex/64a6a47231dad79eba2f24c1f44a8944025c9190.png)
![$ n- $](/files/tex/9f4c49c23e585a667c6d943f0d97a3d2416385ae.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G^{\frac{m}{n}}\isdef (G^{\frac{1}{n}})^m $](/files/tex/567dfd6e8bf6a80c1713f00fdf102fe2c37cec99.png)
Conjecture. Let
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \Delta(G)\geq3 $](/files/tex/c60c049e82d50db3238aff4614e5bd6fc62a2366.png)
![$ m $](/files/tex/ddaab6dc091926fb1da549195000491cefae85c1.png)
![$ n>m $](/files/tex/0bcf0bea4bd5d0169dff13d96d15269bb8e8cf09.png)
![$ \chi(G^{\frac{m}{n}})=\omega(G^\frac{m}{n}) $](/files/tex/891a81b310d1a25bb6a83e21c9c48cbe23864d58.png)
In [1], it was shown that this conjecture is true in some special cases.
Keywords: chromatic number, fractional power of graph, clique number
Partial List Coloring ★★★
Author(s): Iradmusa
Let be a simple graph, and for every list assignment
let
be the maximum number of vertices of
which are colorable with respect to
. Define
, where the minimum is taken over all list assignments
with
for all
.
Conjecture [2] Let
be a graph with list chromatic number
and
. Then
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ \chi_\ell $](/files/tex/46e2d5b6cf87b7e24d9ac72345043107b7ccae3a.png)
![$ 1\leq r\leq s\leq \chi_\ell $](/files/tex/a3fc6cd4c98fabb35869474a493492a0435792e7.png)
![\[\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.\]](/files/tex/47be18e956355dd433b88b66eabf01a9e3ed5f61.png)
Keywords: list assignment; list coloring
![Syndicate content Syndicate content](/misc/feed.png)