Graphs of Large Girth with Prescribed Partial Circular Colourings

This paper completes the constructive proof of the following result: Suppose p/q2 is a rational number, A is a finite set and f₁,f₂,···,f_n are mappings from A to {0,1,···,p–1}. Then for any integer g, there is a graph G=(V,E) of girth at least g with such that G has exactly n (p,q)-colourings (up to equivalence) g₁,g₂,···,g_n, and each g_i is an extension of f_i. A probabilistic proof of this result was given in [8]. A constructive proof of the case p/q3 was given in [7].This research was partially supported by the National Science Council under grant NSC91-2115-M-110-004     

Acyclic Chromatic Indices of Planar Graphs with Girth At Least 4

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiamik (Math. Slovaca 28 (1978), 139–145) and later Alon et al. (J Graph Theory 37 (2001), 157–167) conjectured that for any simple graph G with maximum degree Δ. In this article, we confirm this conjecture for planar graphs of girth at least 4.     

大围长图的广义无圈染色

图的顶点染色称为是r-无圈的,如果它是正常染色,使得每一个圈C上顶点的颜色数至少为min{|C|,r}.图G的r-无圈染色数是图G的r-无圈染色中所用的最少的颜色数.我们证明了对于任意的r≥4,最大度为△、围长至少为2(r-1)△的图G的r-无圈染色数至多为6(r-1)△.     

n-Tuple Coloring of Planar Graphs with Large Odd Girth

 The main result of the papzer is that any planar graph with odd girth at least 10k−7 has a homomorphism to the Kneser graph G _k ^{2 k +1}, i.e. each vertex can be colored with k colors from the set {1,2,…,2k+1} so that adjacent vertices have no colors in common. Thus, for example, if the odd girth of a planar graph is at least 13, then the graph has a homomorphism to G ₂ ⁵, also known as the Petersen graph. Other similar results for planar graphs are also obtained with better bounds and additional restrictions. Received: June 14, 1999 Final version received: July 5, 2000     

Hypohamiltonian Planar Cubic Graphs with Girth 5

A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4‐cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices.     

Edge Coloring of Embedded Graphs with Large Girth

Let G be a simple graph embedded in the surface of Euler characteristic ()0. Denote _e(G), and g the edge chromatic number, the maximum degree and the girth of the graph G, respectively. The paper shows that _e(G)= if 5 and g4, or 4 and g5, or 3 and g9. In addition, if ()>0, then _e(G)= if 3 and g8. Acknowledgments.The authors would like to thank Dr. C.Q. Zhang for carefully reading several versions of this paper during its preparation and for suggesting several stylistic changes that have improved the overall presentation.     

围长至少为5的平面图的线性染色

如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数本文证明了对于每一个最大度为△(G)且围长至少为5的平面图G有lc(G)≤[△(G)/2]+5,并且当△(G)∈{7,8,…,14...     

List 2-distance Coloring of Planar Graphs with Girth Five

Acta Mathematicae Applicatae Sinica, English Series - A 2-distance coloring of a graph is a coloring of the vertices such that two vertices at distance at most two receive distinct colors. A list...     

Generation of Cubic Graphs and Snarks with Large Girth

We describe two new algorithms for the generation of all non‐isomorphic cubic graphs with girth at least that are very efficient for and show how these algorithms can be restricted to generate snarks with girth at least k. Our implementation of these algorithms is more than 30, respectively 40 times faster than the previously fastest generator for cubic graphs with girth at least six and seven, respectively. Using these generators we have also generated all nonisomorphic snarks with girth at least six up to 38 vertices and show that there are no snarks with girth at least seven up to 42 vertices. We present and analyze the new list of snarks with girth 6.     

Topological Subgraphs in Graphs of Large Girth

H of maximum degree , there is an integer g(H) such that every finite graph of minimum degree n and girth at least g(H) contains a subdivision of H. This had been conjectured for in [8]. We prove also that every finite 2n-connected graph of sufficiently large girth is n-linked, and this is best possible for all . Received: February 26, 1997     

Total Colourings of Graphs

We prove that the TCC (Total Colouring Conjecture) is true forcomplete r-partite graphs, which extends a result of M. Rosenfeld.We also give an alternative, slightly simpler proof of an earlierresult (which says that the TCC is true for graphs having maximumdegree 3) obtained independently by M. Rosenfeld and N. Vijayaditya.     

Planar Digraphs without Large Acyclic Sets

Given a directed graph, an acyclic set is a set of vertices inducing a directed subgraph with no directed cycle. In this note, we show that for all integers , there exist oriented planar graphs of order n and digirth g for which the size of the maximum acyclic set is at most . When this result disproves a conjecture of Harutyunyan and shows that a question of Albertson is best possible.     

Dense Minors In Graphs Of Large Girth

We show that a graph of girth greater than 6 log k+3 and minimum degree at least 3 has a minor of minimum degree greater than k. This is best possible up to a factor of at most 9/4. As a corollary, every graph of girth at least 6 log r+3 log log r+c and minimum degree at least 3 has a K _r minor.     

An Oriented 6-Coloring of Planar Graphs with Girth at Least 9

We prove that every oriented graph with a maximum average degree less than 18/7 admits a homomorphism into \(P_{7}^{*}\), the Paley tournament of order seven with one vertex deleted. In particular, every oriented planar graph of girth at least 9 has a homomorphism into \(P_{7}^{*}\), whence every planar graph of girth at least 9 has oriented chromatic number at most 6.     

围长至少为4的平面图的邻点可区别边色数

图G的邻点可区别边染色是G的正常边染色,使得每一对相邻顶点有不同的颜色集合．G的邻点可区别边色数X＇a（G）是使得G有一个k-邻点可区别边染色的最小正整数七．本文证明了：若G是围长至少为4且最大度至少为6的平面图,则X＇a（G）≤△＋2．     

不含相邻三角形的平面图的无圈边着色

An acyclic edge coloring of a graph G is a proper edge coloring such that there are no bichromatic cycles.The acyclic edge chromatic number of a graph G is the minimum number k such that there exists an acyclic edge coloring using k colors and is denoted by χ’ a(G).In this paper we prove that χ ’ a(G) ≤(G) + 5 for planar graphs G without adjacent triangles.     

Acyclic Edge Coloring of Planar Graphs Without Small Cycles

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ≤ Δ(G) + 2 for any graphs. In this paper, it is shown that the conjecture holds for planar graphs without 4- and 5-cycles or without 4- and 6-cycles.     

Homomorphism Bounds for Oriented Planar Graphs of Given Minimum Girth

We find necessary conditions for a digraph H to admit a homomorphism from every oriented planar graph of girth at least n, and use these to prove the existence of a planar graph of girth 6 and oriented chromatic number at least 7. We identify a ${\overleftrightarrow{K_4}}$ -free digraph of order 7 which admits a homomorphism from every oriented planar graph (here ${\overleftrightarrow{K_n}}$ means a digraph with n vertices and arcs in both directions between every distinct pair), and a ${\overleftrightarrow{K_3}}$ -free digraph of order 4 which admits a homomorphism from every oriented planar graph of girth at least 5.     

Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths

Recently, Borodin, Kostochka, and Yancey (Discrete Math 313(22) (2013), 2638–2649) showed that the vertices of each planar graph of girth at least 7 can be 2‐colored so that each color class induces a subgraph of a matching. We prove that any planar graph of girth at least 6 admits a vertex coloring in colors such that each monochromatic component is a path of length at most 14. Moreover, we show a list version of this result. On the other hand, for each positive integer , we construct a planar graph of girth 4 such that in any coloring of vertices in colors there is a monochromatic path of length at least t. It remains open whether each planar graph of girth 5 admits a 2‐coloring with no long monochromatic paths.