Equivalently: is the star chromatic index of linear in ?
The star chromatic index of a graph is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored.
Since can be replaced by a smaller value, we can also write the conjecture as, for any positive ,
Keywords: Goodstein Sequence
Let denote the diagonal Ramsey number.
Keywords: Ramsey number
Author(s): David Eppstein
Keywords: knot theory, links, chessboard complex
Given a Matrix , the -th elementary symmetric function of , namely , is defined as the sum of all -by- principal minors.
Find a closed expression for the -th elementary symmetric function of a sum of N -by- matrices, with by using partitions.
If is a finite set of points which is 2-colored, an empty triangle is a set with so that the convex hull of is disjoint from . We say that is monochromatic if all points in are the same color.
We let denote the -dimensional cube graph. A map is called edge-antipodal if whenever are antipodal edges.
The famous 0-1 Knapsack problem is: Given and integers, determine whether or not there are values so that
The best known worst-case algorithm runs in time times a polynomial in . Is there an algorithm that runs in time ?
Is there an algorithm that decides, for input graphs and , whether there exists a homomorphism from to in time for some constant ?
Begin with the generating function for unrestricted partitions:
Now change some of the plus signs to minus signs. The resulting series will have coefficients congruent, mod 2, to the coefficients of the generating series for unrestricted partitions. I conjecture that the signs may be chosen such that all the coefficients of the series are either 1, -1, or zero.
For let denote the minimal number such that there is a rainbow in every equinumerous -coloring of for every
The deck of a graph is the multiset consisting of all unlabelled subgraphs obtained from by deleting a vertex in all possible ways (counted according to multiplicity).