An interval coloring of a graph G is a proper coloring of E(G) by positive integers such that the colors on the edges incident to any vertex are consecutive. A (3,4)-biregular bigraph is a bipartite graph in which each vertex of one part has degree 3 and each vertex of the other has degree 4; it is unknown whether these all have interval colorings. We prove that G has an interval coloring using 6 colors when G is a (3,4)-biregular bigraph having a spanning subgraph whose components are paths with endpoints at 3-valent vertices and lengths in {2, 4, 6, 8}. We provide several sufficient conditions for the existence of such a subgraph.

In the first part of this article, we employ Thomason's Lollipop Lemma [25] to prove that bridgeless cubic graphs containing a spanning lollipop admit a cycle double cover (CDC) containing the circuit in the lollipop; this implies, in particular, that bridgeless cubic graphs with a 2-factor F having two components admit CDCs containing any of the components in the 2-factor, although it need not have a CDC containing all of F. As another example consider a cubic bridgeless graph containing a 2-factor with three components, all induced circuits. In this case, two of the components may separately be used to start a CDC although it is uncertain whether the third component may be part of some CDC. Numerous other corollaries shall be given as well. In the second part of the article, we consider special types of bridgeless cubic graphs for which a prominent circuit can be shown to be included in a CDC. The interest here is the proof technique and therefore we only give the simplest case of the theorem. Notably, we show that a cubic graph that consists of an induced 2k-circuit C together with an induced 4k-circuit T and an independent set of 2k vertices, each joined by one edge to C and two edges to T, has a CDC starting with T.

For ordinary graphs it is known that any graph G with more edges than the Turan number of Ks must contain several copies of Ks, and a copy of Ks+1-, the complete graph on s+1 vertices with one missing edge. Erdos asked if the same result is true for Ks3, the complete 3-uniform hypergraph on s vertices. In this note, we show that for small values of n, the number of vertices in G, the answer is negative for s=4. For the second property, that of containing a Ks+13-, we show that for s=4 the answer is negative for all large n as well, by proving that the Turan density of K53- is greater than that of K43.

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

chi-bounds, operations, and chords2018In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 88, no 2, p. 312-336Article in journal (Refereed)

Abstract [en]

A long unichord in a graph is an edge that is the unique chord of some cycle of length at least 5. A graph is long unichord free if it does not contain any long unichord. We prove a structure theorem for long unichord free graph. We give an O(n4m) time algorithm to recognize them. We show that any long unichord free graph G can be colored with at most O(3) colors, where is the maximum number of pairwise adjacent vertices in G.