Search

Results 1-20 of 43

Algebra

Text loans@http://www.loansintheuk.co.uk/text-loans.html ★★

Author(s):

12 month loans, 12 month payday loans, text loans, same payday loans

Keywords:

Posted by kwhite058
updated October 19th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Choosability of Graph Powers ★★

Author(s): Noel

Question (Noel, 2013) Does there exist a function $f(k)=o(k^2)$ such that for every graph $G$ , $\text{ch}\left(G^2\right)\leq f\left(\chi\left(G^2\right)\right)?$

Keywords: choosability; chromatic number; list coloring; square of a graph

Posted by Jon Noel
updated July 13th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Bounding the on-line choice number in terms of the choice number ★★

Author(s): Zhu

Question Are there graphs for which $\text{ch}^{\text{OL}}-\text{ch}$ is arbitrarily large?

Keywords: choosability; list coloring; on-line choosability

Posted by Jon Noel
updated April 11th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Choice Number of k-Chromatic Graphs of Bounded Order ★★

Author(s): Noel

Conjecture If $G$ is a $k$ -chromatic graph on at most $mk$ vertices, then $\text{ch}(G)\leq \text{ch}(K_{m*k})$ .

Keywords: choosability; complete multipartite graph; list coloring

Posted by Jon Noel
updated February 2nd, 2013

add new comment

Logic » Finite Model Theory

Order-invariant queries ★★

Author(s): Segoufin

Question

${<}\text{-invariant\:FO} = \text{FO}$

${<}\text{-invariant\:FO}$

$\text{MSO}$

${<}\text{-invariant\:FO}$

Keywords: Effective syntax; FMT12-LesHouches; Locality; MSO; Order invariance

Posted by dberwanger
updated May 18th, 2012

add new comment

Graph Theory

Fractional Hadwiger ★★

Author(s): Harvey; Reed; Seymour; Wood

Conjecture For every graph $G$ ,
(a) $\chi_f(G)\leq\text{had}(G)$
(b) $\chi(G)\leq\text{had}_f(G)$
(c) $\chi_f(G)\leq\text{had}_f(G)$ .

Keywords: fractional coloring, minors

Posted by David Wood
updated March 16th, 2014

add new comment

Graph Theory » Extremal G.T.

Weak saturation of the cube in the clique ★

Author(s): Morrison; Noel

Problem

Determine $\text{wsat}(K_n,Q_3)$ .

Keywords: bootstrap percolation; hypercube; Weak saturation

Posted by Jon Noel
updated April 6th, 2016

add new comment

Graph Theory

Shuffle-Exchange Conjecture (graph-theoretic form) ★★★

Author(s): Beneš; Folklore; Stone

Given integers $k,n \ge 2$ , the 2-stage Shuffle-Exchange graph/network, denoted $\text{SE}(k,n)$ , is the simple $k$ -regular bipartite graph with the ordered pair $(U,V)$ of linearly labeled parts $U:=\{u_0,\dots,u_{t-1}\}$ and $V:=\{v_0,\dots,v_{t-1}\}$ , where $t:=k^{n-1}$ , such that vertices $u_i$ and $v_j$ are adjacent if and only if $(j - ki) \text{ mod } t < k$ (see Fig.1).

Given integers $k,n,r \ge 2$ , the $r$ -stage Shuffle-Exchange graph/network, denoted $(\text{SE}(k,n))^{r-1}$ , is the proper (i.e., respecting all the orders) concatenation of $r-1$ identical copies of $\text{SE}(k,n)$ (see Fig.1).

Let $r(k,n)$ be the smallest integer $r\ge 2$ such that the graph $(\text{SE}(k,n))^{r-1}$ is rearrangeable.

Problem Find $r(k,n)$ .

Conjecture $r(k,n)=2n-1$ .

Keywords:

Posted by Vadim Lioubimov
updated October 30th, 2009

add new comment

Graph Theory » Topological G.T. » Crossing numbers

Are different notions of the crossing number the same? ★★★

Author(s): Pach; Tóth

Problem Does the following equality hold for every graph $G$ ? $\text{pair-cr}(G) = \text{cr}(G)$

The crossing number $\text{cr}(G)$ of a graph $G$ is the minimum number of edge crossings in any drawing of $G$ in the plane. In the pairwise crossing number $\text{pair-cr}(G)$ , we minimize the number of pairs of edges that cross.

Keywords: crossing number; pair-crossing number

Posted by cibulka
updated November 3rd, 2009

add new comment

Graph Theory » Coloring » Edge coloring

Strong edge colouring conjecture ★★

Author(s): Erdos; Nesetril

A strong edge-colouring of a graph $G$ is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to distinct edges with the same colour are not adjacent. The strong chromatic index $s\chi'(G)$ is the minimum number of colours in a strong edge-colouring of $G$ .

Conjecture $s\chi'(G) \leq \frac{5\Delta^2}{4}, \text{if $\Delta$ is even,}$ $s\chi'(G) \leq \frac{5\Delta^2-2\Delta +1}{4},&\text{if $\Delta$ is odd.}$

Keywords:

Posted by fhavet
updated March 1st, 2013

add new comment

Graph Theory » Coloring » Homomorphisms

Circular choosability of planar graphs ★

Author(s): Mohar

Let $G = (V, E)$ be a graph. If $p$ and $q$ are two integers, a $(p,q)$ -colouring of $G$ is a function $c$ from $V$ to $\{0,\dots,p-1\}$ such that $q \le |c(u)-c(v)| \le p-q$ for each edge $uv\in E$ . Given a list assignment $L$ of $G$ , i.e.~a mapping that assigns to every vertex $v$ a set of non-negative integers, an $L$ -colouring of $G$ is a mapping $c : V \to N$ such that $c(v)\in L(v)$ for every $v\in V$ . A list assignment $L$ is a $t$ - $(p,q)$ -list-assignment if $L(v) \subseteq \{0,\dots,p-1\}$ and $|L(v)| \ge tq$ for each vertex $v \in V$ . Given such a list assignment $L$ , the graph G is $(p,q)$ - $L$ -colourable if there exists a $(p,q)$ - $L$ -colouring $c$ , i.e. $c$ is both a $(p,q)$ -colouring and an $L$ -colouring. For any real number $t \ge 1$ , the graph $G$ is $t$ - $(p,q)$ -choosable if it is $(p,q)$ - $L$ -colourable for every $t$ - $(p,q)$ -list-assignment $L$ . Last, $G$ is circularly $t$ -choosable if it is $t$ - $(p,q)$ -choosable for any $p$ , $q$ . The circular choosability (or circular list chromatic number or circular choice number) of G is $cch(G) := \inf\{t \ge 1 : G \text{ is circularly $t$-choosable}\}.$

Problem What is the best upper bound on circular choosability for planar graphs?

Keywords: choosability; circular colouring; planar graphs

Posted by rosskang
updated August 23rd, 2012

add new comment

Number Theory

Alexa's Conjecture on Primality ★★

Author(s): Alexa

Definition Let $r_i$ be the unique integer (with respect to a fixed $p\in\mathbb{N}$ ) such that

$(2i+1)^{p-1} \equiv r_i \pmod p ~~\text{ and } ~ 0 \le r_i < p.$

Conjecture A natural number $p \ge 8$ is a prime iff $\displaystyle \sum_{i=1}^{\left \lfloor \frac{\sqrt[3]p}{2} \right \rfloor} r_i = \left \lfloor \frac{\sqrt[3]p}{2} \right \rfloor$

Keywords: primality

Posted by princeps
updated June 14th, 2013

7 comments

Graph Theory

Book Thickness of Subdivisions ★★

Author(s): Blankenship; Oporowski

Let $G$ be a finite undirected simple graph.

A $k$ -page book embedding of $G$ consists of a linear order $\preceq$ of $V(G)$ and a (non-proper) $k$ -colouring of $E(G)$ such that edges with the same colour do not cross with respect to $\preceq$ . That is, if $v\prec x\prec w\prec y$ for some edges $vw,xy\in E(G)$ , then $vw$ and $xy$ receive distinct colours.

One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.

The book thickness of $G$ , denoted by bt $(G)$ is the minimum integer $k$ for which there is a $k$ -page book embedding of $G$ .

Let $G'$ be the graph obtained by subdividing each edge of $G$ exactly once.

Conjecture There is a function $f$ such that for every graph $G$ , $\text{bt}(G) \leq f( \text{bt}(G') )\enspace.$

Keywords: book embedding; book thickness

Posted by David Wood
updated July 10th, 2021

1 comment

Logic » Finite Model Theory

Monadic second-order logic with cardinality predicates ★★

Author(s): Courcelle

The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic formulas:

$\text{``}\,\mathrm{Card}(X) = \mathrm{Card}(Y)\,\text{''}$

$\text{``}\,\mathrm{Card}(X) \text{ belongs to } A\,\text{''}$

where $A$ is a fixed recursive set of integers.

Let us fix $k$ and a closed formula $F$ in this language.

Conjecture Is it true that the validity of $F$ for a graph $G$ of tree-width at most $k$ can be tested in polynomial time in the size of $G$ ?

Keywords: bounded tree width; cardinality predicates; FMT03-Bedlewo; MSO

Posted by dberwanger
updated May 18th, 2012

add new comment

Graph Theory » Coloring » Vertex coloring

On-Line Ohba's Conjecture ★★

Author(s): Huang; Wong; Zhu

Conjecture If $|V(G)|\leq 2\chi(G)$ , then the on-line choice number of $G$ is equal to $\chi(G)$ .

Keywords: choosability; list coloring; on-line choosability

Posted by Jon Noel
updated April 11th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Choice number of complete multipartite graphs with parts of size 4 ★

Author(s):

Question What is the choice number of $K_{4*k}$ for general $k$ ?

Keywords: choosability; complete multipartite graph; list coloring

Posted by Jon Noel
updated April 11th, 2013

add new comment

Algebra

Samsung Galaxy S2 Bargains: Take hold of most exclusive offers and also rewards@http://www.galaxyseries.co.uk ★★

Author(s):

Due to the completely new amazing cell gadget, Samsung offers collaborated together with most top cell system services to provide very best on the phone offers on the people. These types of offers include the least expensive of methods allow you procure this particular exclusive sensational convenient gadget by Samsung at affordable conditions.

Keywords:

Posted by galaxyseriesuk
updated November 8th, 2013

add new comment

Graph Theory

Sidorenko's Conjecture ★★★

Author(s): Sidorenko

Conjecture For any bipartite graph $H$ and graph $G$ , the number of homomorphisms from $H$ to $G$ is at least $\left(\frac{2|E(G)|}{|V(G)|^2}\right)^{|E(H)|}|V(G)|^{|V(H)|}$ .