I came up with this original conjecture several years ago, and the formal wording below about a year afterwards.
My conjecture:
For all primes $P$, there exists a $P$-color edge coloring of the $2(P^2+P+1)$-vertex crown graph with no monochromatic cycles of length 4.
An equivalent conjecture which is not at all obviously equivalent (and is much harder to state, but is much more visual) is as follows:
For all primes $P$, a square checkerboard measuring $P^2+P+1$ units on a side may be colored with $P$ different colors (however, leaving all squares on the diagonal blanked out) such that no rectangle comprised of checkerboard squares shall have all four corners the same color.
I have only been able to demonstrate this for $P=2$ and have struggled to demonstrate it for $P=3$. (I haven't attempted a computer-assisted proof.) I feel that this conjecture is likely true, but I am not certain.
What I do know for certain (it's quite easy) is that for all primes $P$, it is possible to generate a $2(P^2+P+1)$-vertex bipartite graph such that each vertex has a degree of $P+1$ and there is no cycle of length 4. Such a graph is equivalent to a single color subgraph of the conjectured graph type described by the bolded sentence above.
This is related to finite projective planes in some way, and even more closely related to symmetric balanced incomplete block designs of which finite projective planes are only one type. Also, the Heawood Graph appears related as well.
I think an equivalent statement to the conjecture above is: For all primes $P$, the $2(P^2+P+1)$-vertex crown graph can be partitioned into $P$ subgraphs with girth 6, radius 3, diameter 3, chromatic number 2.
Any one of these subgraphs is easy to generate. It's partitioning the crown graph into them (and proving that it can be so partitioned) that is giving me difficulty.
How can I set about proving or disproving this conjecture, or (if disproving it) characterizing the set of primes for which it is true?
As pointed out by Paul Hudford in the comments, this can be restated as a graph packing problem.
Definition of "pack" (taken from this PDF):
Let $G_i = (V_i, E_i)$ be graphs of order at most $n$, where $i= 1, . . . , k$.
$G_1, . . . , G_k$ are said to pack if there exist injective mappings of the vertex sets into $[n]$, $V_i \rightarrow [n] ={1,2, . . . , n}$ such that the images of the edge sets do not intersect.
In layman's terms, given a bunch of graphs, if you can draw all the graphs using the same set of (unlabelled) nodes without ending up drawing any particular edge more than once, the graphs "pack."
My question involves taking a particular type of graph and counting how many times it can be packed with itself.
For any prime $P$, let $G_P$ be a graph representing the finite projective plane of order $P$.
In particular, let $G_P$ be a bipartite graph with $2(P^2 + P+1)$ vertices, where each vertex has degree $P+1$ and there is no cycle of length 4. This represents a finite projective plane if one considers that the left-hand vertices represent points and the right-hand vertices represent lines; then the edges represent that a given line passes through a given point.
(Or to be more formal about it, call the left-hand vertices $L_1$ through $L_{P^2+P+1}$ to represent lines, and call the right-hand vertices $Q_1$ through $Q_{P^2+P+1}$ to represent points. Then line $L_i$ passes through point $Q_j$ if and only if there is an edge connecting $L_i$ and $Q_j$. Also note that since any two lines in a projective plane meet in one and only one point and any two points define a single line, likewise for any two nodes chosen on one side or the other of $G_P$, there is one and only one node to which they are both adjacent; hence no cycles of length 4.)
The question, then, is for each prime $P$, how many instances of $G_P$ can be packed together?
The upper limit is $P$ for any prime $P$ (simply by a count of edges). However, it is unclear if this upper limit is actually attainable for any $P$ greater than $2$.