The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Displaying 81 –
100 of
715
Lebesgue (1940) proved that every 3-polytope P5 of girth 5 has a path of three vertices of degree 3. Madaras (2004) refined this by showing that every P5 has a 3-vertex with two 3-neighbors and the third neighbor of degree at most 4. This description of 3-stars in P5s is tight in the sense that no its parameter can be strengthened due to the dodecahedron combined with the existence of a P5 in which every 3-vertex has a 4-neighbor. We give another tight description of 3-stars in P5s: there is a vertex...
Let f(n, p, q) be the minimum number of colors necessary to color the edges of Kn so that every Kp is at least q-colored. We improve current bounds on these nearly “anti-Ramsey” numbers, first studied by Erdös and Gyárfás. We show that [...] , slightly improving the bound of Axenovich. We make small improvements on bounds of Erdös and Gyárfás by showing [...] and for all even n ≢ 1(mod 3), f(n, 4, 5) ≤ n− 1. For a complete bipartite graph G= Kn,n, we show an n-color construction to color the edges...
Let G = (V(G), E(G)) be a connected multigraph and let h(G) be the minimum integer k such that for every edge-colouring of G, using exactly k colours, there is at least one edge-cut of G all of whose edges receive different colours. In this note it is proved that if G has at least 2 vertices and has no bridges, then h(G) = |E(G)| -|V(G)| + 2.
In 1955, Kotzig proved that every 3-connected planar graph has an edge with the degree sum of its end vertices at most 13, which is tight. An edge uv is of type (i, j) if d(u) ≤ i and d(v) ≤ j. Borodin (1991) proved that every normal plane map contains an edge of one of the types (3, 10), (4, 7), or (5, 6), which is tight. Cole, Kowalik, and Škrekovski (2007) deduced from this result by Borodin that Kotzig’s bound of 13 is valid for all planar graphs with minimum degree δ at least 2 in which every...
We present a new proof of Whitney's broken circuit theorem based on induction on the number of edges and the deletion-contraction formula.
The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph −G⃗ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of −G⃗ receive distinct sums of outgoing...
We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.
We present an overview of the theory of nowhere zero flows, in particular the duality of flows and colorings, and the extension to antiflows and strong oriented colorings. As the main result, we find the asymptotic relation between oriented and strong oriented chromatic number.
The homomorphisms of oriented or undirected graphs, the oriented chromatic number, the relationship between acyclic colouring number and oriented chromatic number, have been recently intensely studied. For the purpose of duality, we define the notions of strong-oriented colouring and antisymmetric-flow. An antisymmetric-flow is a flow with values in an additive abelian group which uses no opposite elements of the group. We prove that the strong-oriented chromatic number (as the modular version...
Currently displaying 81 –
100 of
715