Colourings of graphs with two consecutive odd cycle lengths

In 1992 Gyárfás showed that a graph G having only k odd cycle lengths is (2k+1)-colourable, if it does not contain a K_2k+2. In this paper, we will present the results for graphs containing only odd cycles of length 2m−1 and 2m+1 as done in [S. Matos Camacho, Colourings of graph with prescribed cycle lengths, diploma thesis, TU Bergakademie Freiberg, 2006. [3]]. We will show that these graphs are 4-colourable.     

On the oriented chromatic number of graphs with given excess

The excess of a graph G is defined as the minimum number of edges that must be deleted from G in order to get a forest. We prove that every graph with excess at most k has chromatic number at most and that this bound is tight. Moreover, we prove that the oriented chromatic number of any graph with excess k is at most k+3, except for graphs having excess 1 and containing a directed cycle on 5 vertices which have oriented chromatic number 5. This bound is tight for k?4.     

Homomorphisms and amalgamation

We prove that for each finite core graph G, the class of all graphs admitting a homomorphism into G is a pseudo-amalgamation class, in the sense of Fraı̈ssé. This fact gives rise to a countably infinite universal pseudo-homogeneous graph which shares some of the properties of the infinite random graph. Our methods apply simultaneously to G-colourings in several classes of relational structures, such as the classes of directed graphs or hypergraphs.     

Nonseparating trees in 2-connected graphs and oriented trees in strongly connected digraphs

Mader (2010) conjectured that for every positive integer $k$ and every finite tree $T$ with order $m$, every $k$-connected, finite graph $G$ with $\delta \left(G\right)\ge \lfloor \frac{3}{2}k\rfloor +m-1$ contains a subtree $T^{\prime }$ isomorphic to $T$ such that $G-V\left(T^{\prime }\right)$ is $k$-connected. The conjecture has been verified for paths, trees when $k=1$, and stars or double-stars when $k=2$. In this paper we verify the conjecture for two classes of trees when $k=2$.For digraphs, Mader (2012) conjectured that every $k$-connected digraph $D$ with minimum semi-degree $\delta \left(D\right)=min\{{\delta }^{+}\left(D\right),{\delta }^{-}\left(D\right)\}\ge 2k+m-1$ for a positive integer $m$ has a dipath $P$ of order $m$ with $\kappa (D-V\left(P\right))\ge k$. The conjecture has only been verified for the dipath with $m=1$, and the dipath with $m=2$ and $k=1$. In this paper, we prove that every strongly connected digraph with minimum semi-degree $\delta \left(D\right)=min\{{\delta }^{+}\left(D\right),{\delta }^{-}\left(D\right)\}\ge m+1$ contains an oriented tree $T$ isomorphic to some given oriented stars or double-stars with order $m$ such that $D-V\left(T\right)$ is still strongly connected.     

Colourings of cubic graphs inducing isomorphic monochromatic subgraphs

A -bisection of a bridgeless cubic graph is a -colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes ( monochromatic components in what follows) have order at most . Ban and Linial Conjectured that every bridgeless cubic graph admits a -bisection except for the Petersen graph. A similar problem for the edge set of cubic graphs has been studied: Wormald conjectured that every cubic graph with has a -edge colouring such that the two monochromatic subgraphs are isomorphic linear forests (ie, a forest whose components are paths). Finally, Ando conjectured that every cubic graph admits a bisection such that the two induced monochromatic subgraphs are isomorphic. In this paper, we provide evidence of a strong relation of the conjectures of Ban-Linial and Wormald with Ando's Conjecture. Furthermore, we also give computational and theoretical evidence in their support. As a result, we pose some open problems stronger than the above-mentioned conjectures. Moreover, we prove Ban-Linial's Conjecture for cubic-cycle permutation graphs. As a by-product of studying -edge colourings of cubic graphs having linear forests as monochromatic components, we also give a negative answer to a problem posed by Jackson and Wormald about certain decompositions of cubic graphs into linear forests.     

Completely connected clustered graphs

Planar drawings of clustered graphs are considered. We introduce the notion of completely connected clustered graphs, i.e., hierarchically clustered graphs that have the property that not only every cluster but also each complement of a cluster induces a connected subgraph. As a main result, we prove that a completely connected clustered graph is c-planar if and only if the underlying graph is planar. Further, we investigate the influence of the root of the inclusion tree to the choice of the outer face of the underlying graph and vice versa.     

Minimum path decompositions of oriented cubic graphs

Pullman [3] conjectured that if k is an odd positive integer, then every orientation of a regular graph of degree k has a minimum decomposition which contains no vertex which is both the initial vertex of some path in the decomposition and the terminal vertex of some other path in the decomposition. In this paper, the conjecture is established for cubic graphs, and its connection with Kelly's conjecture for tournaments is described.     

On the inducibility of oriented graphs on four vertices

We consider the problem of determining the inducibility (maximum possible asymptotic density of induced copies) of oriented graphs on four vertices. We provide exact values for more than half of the graphs, and very close lower and upper bounds for all the remaining ones. It occurs that, for some graphs, the structure of extremal constructions maximizing density of its induced copies is very sophisticated and complex.     

Properties of connected graphs having minimum degree distance

The degree distance of a connected graph, introduced by Dobrynin, Kochetova and Gutman, has been studied in mathematical chemistry. In this paper some properties of graphs having minimum degree distance in the class of connected graphs of order n and size m≥n−1 are deduced. It is shown that any such graph G has no induced subgraph isomorphic to P₄, contains a vertex z of degree n−1 such that G−z has at most one connected component C such that |C|≥2 and C has properties similar to those of G.For any fixed k such that k=0,1 or k≥3, if m=n+k and n≥k+3 then the extremal graph is unique and it is isomorphic to K₁+(K_1,k+1∪(n−k−3)K₁).     

Geometric representation of cubic graphs with four directions

We show that every connected cubic graph can be drawn in the plane with straight-line edges using only four distinct slopes and disconnected cubic graphs with five distinct slopes.     

Highly connected multicoloured subgraphs of multicoloured graphs

Suppose the edges of the complete graph on n vertices, E(K_n), are coloured using r colours; how large a k-connected subgraph are we guaranteed to find, which uses only at most s of the colours? This question is due to Bollobás, and the case s=1 was considered in Liu et al. [Highly connected monochromatic subgraphs of multicoloured graphs, J. Graph Theory, to appear]. Here we shall consider the case s2, proving in particular that when s=2 and r+1 is a power of 2 then the answer lies between 4n/(r+1)-17kr(r+2k+1) and 4n/(r+1)+4, that if r=2s+1 then the answer lies between and , and that phase transitions occur at s=r/2 and . We shall also mention some of the more glaring open problems relating to this question.     

Generating unlabeled connected cubic planar graphs uniformly at random

We present an expected polynomial time algorithm to generate an unlabeled connected cubic planar graph uniformly at random. We first consider rooted connected cubic planar graphs, i.e., we count connected cubic planar graphs up to isomorphisms that fix a certain directed edge. Based on decompositions along the connectivity structure, we derive recurrence formulas for the exact number of rooted cubic planar graphs. This leads to rooted 3‐connected cubic planar graphs, which have a unique embedding on the sphere. Special care has to be taken for rooted graphs that have a sense‐reversing automorphism. Therefore we introduce the concept of colored networks, which stand in bijective correspondence to rooted 3‐connected cubic planar graphs with given symmetries. Colored networks can again be decomposed along the connectivity structure. For rooted 3‐connected cubic planar graphs embedded in the plane, we switch to the dual and count rooted triangulations. Since all these numbers can be evaluated in polynomial time using dynamic programming, rooted connected cubic planar graphs can be generated uniformly at random in polynomial time by inverting the decomposition along the connectivity structure. To generate connected cubic planar graphs without a root uniformly at random, we apply rejection sampling and obtain an expected polynomial time algorithm. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Extensions on 2-edge connected 3-regular up-embeddable graphs

1.IntroductionLetHbea3-regulargraph.Forel,e2,e3EE(H)(el,eZande3areallowedtobethesame),weaddthreenewvenicesal)wZandw3inel,eZande3respectively.ChoosingueV(H),andthenjoiningutofi(i=1,2,3),weatlastobtaina3-regulargraphG.Or,inotherwords,wesaythatGisobtainedfromHbyanM-extension.DenoteG=M(u)(H)(seeFig.1).LetHbea3-regulargraph.Takingel,eZEE(H)(elandeZareallowedtobethesame),weputtwodistinctvenicestvian0dwZinelandeZrespectively,andaddtwodistinctvenicesu,v4V(H),thenjoinutoal,joinvtowZandjoin…     

Bandwidth of the strong product of two connected graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(x)-f(y)|:xy∈E(G)} taken over all proper numberings f of G. The strong product of two graphs G and H, written as G(S_P)H, is the graph with vertex set V(G)×V(H) and with (u₁,v₁) adjacent to (u₂,v₂) if one of the following holds: (a) u₁ and v₁ are adjacent to u₂ and v₂ in G and H, respectively, (b) u₁ is adjacent to u₂ in G and v₁=v₂, or (c) u₁=u₂ and v₁ is adjacent to v₂ in H. In this paper, we investigate the bandwidth of the strong product of two connected graphs. Let G be a connected graph. We denote the diameter of G by D(G). Let d be a positive integer and let x,y be two vertices of G. Let denote the set of vertices v so that the distance between x and v in G is at most d. We define δ_d(G) as the minimum value of over all vertices x of G. Let denote the set of vertices z such that the distance between x and z in G is at most d-1 and z is adjacent to y. We denote the larger of and by . We define η(G)=1 if G is complete and η(G) as the minimum of over all pair of vertices x,y of G otherwise. Let G and H be two connected graphs. Among other results, we prove that if δ_D(H)(G)?B(G)D(H)+1 and B(H)=⌈(|V(H)|+η(H)-2)/D(H)⌉, then B(G(S_P)H)=B(G)|V(H)|+B(H). Moreover, we show that this result determines the bandwidth of the strong product of some classes of graphs. Furthermore, we study the bandwidth of the strong product of power of paths with complete bipartite graphs.     

A linear algorithm for minimum 1-identifying codes in oriented trees

Consider an oriented graph G=(V,A), a subset of vertices C⊆V, and an integer r?1; for any vertex v∈V, let denote the set of all vertices x such that there exists a path from x to v with at most r arcs. If for all vertices v∈V, the sets are all nonempty and different, then we call C an r-identifying code. We describe a linear algorithm which gives a minimum 1-identifying code in any oriented tree.     

An oriented coloring of planar graphs with girth at least five

An oriented k-coloring of an oriented graph G is a homomorphism from G to an oriented graph H of order k. We prove that every oriented graph with a maximum average degree less than and girth at least 5 has an oriented chromatic number at most 16. This implies that every oriented planar graph with girth at least 5 has an oriented chromatic number at most 16, that improves the previous known bound of 19 due to Borodin et al. [O.V. Borodin, A.V. Kostochka, J. Nešet?il, A. Raspaud, É. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math. 206 (1999) 77-89].