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
Graph Theory » Coloring » Vertex coloring

Double-critical graph conjecture ★★

Author(s): Erdos; Lovasz

A connected simple graph $ G $ is called double-critical, if removing any pair of adjacent vertexes lowers the chromatic number by two.

Conjecture   $ K_n $ is the only $ n $-chromatic double-critical graph

Keywords: coloring; complete graph

Posted by DFR
updated November 30th, 2009
2 comments
Algebra

Elementary symmetric of a sum of matrices ★★★

Author(s):

Problem  

Given a Matrix $ A $, the $ k $-th elementary symmetric function of $ A $, namely $ S_k(A) $, is defined as the sum of all $ k $-by-$ k $ principal minors.

Find a closed expression for the $ k $-th elementary symmetric function of a sum of N $ n $-by-$ n $ matrices, with $ 0\le N\le k\le n $ by using partitions.

Keywords:

Posted by rscosa
updated August 27th, 2010
1 comment
Number Theory » Combinatorial N.T.

Frobenius number of four or more integers ★★

Author(s):

Problem   Find an explicit formula for Frobenius number $ g(a_1, a_2, \dots, a_n) $ of co-prime positive integers $ a_1, a_2, \dots, a_n $ for $ n\geq 4 $.

Keywords:

Posted by maxal
updated November 26th, 2008
add new comment