Colorings and girth of oriented planar graphs
Let \(G=(V,E)\) and \(H=(V',E')\) be graphs (possibly digraphs). A homomorphism from \(G\) to \(H\) is any mapping \(f:V\to V'\) satisfying \([x,y]\in E\Rightarrow [f(x),f(y)]\in E'.\) Here the brackets on both sides of the implication mean the same thing: either an edge or an arc. The existence of a homomorphism from \(G\) to \(H\) is denoted by \(G\to H\). The following two problems are considered: (A) The oriented coloring problem. Given an oriented graph \(G=(V,A)\), find the smallest number of vertices of an oriented graph \(H\) for which \(G\to H\). This number, denoted by \(\chi(\vec G)\), is called the oriented chromatic number of \(G\). (Note that this is the same as the ordinary chromatic number if we consider symmetric digraphs as target digraphs.) (B) The girth problem. Given an integer \(g>2\), determine the quantity \[ \chi(\vec g)= \max\{\chi(\vec G)\mid G\text{ is planar and has girth }g\}. \] It is shown that every orientation of any large girth planar graph has oriented chromatic number at most 5. Furthermore, the authors classify those digraphs on 3, 4 and 5 vertices which color (i.e. admit a homomorphism from) all large girth oriented planar graphs.
- An oriented coloring of planar graphs with girth at least five
- Homomorphism bounds for oriented planar graphs of given minimum girth
- An oriented colouring of planar graphs with girth at least 4
- Oriented vertex and arc colorings of outerplanar graphs
- An oriented 7-colouring of planar graphs with girth at least 7
- Acyclic and oriented chromatic numbers of graphs
- Acyclic colorings of planar graphs
- Colorings and interpretations: a connection between graphs and grammar forms
- Duality and Polynomial Testing of Tree Homomorphisms
- Every planar map is four colorable
- Good and semi-strong colorings of oriented planar graphs
- Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
- scientific article; zbMATH DE number 3639666 (Why is no real title available?)
- scientific article; zbMATH DE number 878894 (Why is no real title available?)
- scientific article; zbMATH DE number 932194 (Why is no real title available?)
- On acyclic colorings of planar graphs
- On the complexity of H-coloring
- On the oriented game chromatic number
- Some new good characterizations for directed graphs
- The effect of two cycles on the complexity of colourings by directed graphs
- Universality of \(A\)-mote graphs
- On the oriented chromatic number of grids
- An oriented coloring of planar graphs with girth at least five
- Colorings and orientations of graphs
- Homomorphisms of edge-colored graphs and Coxeter groups
- Antisymmetric flows and strong colourings of oriented graphs
- Antisymmetric flows and strong oriented coloring of planar graphs
- Homomorphisms and oriented colorings of equivalence classes of oriented graphs
- Homomorphisms from sparse graphs with large girth.
- On universal graphs for planar oriented graphs of a given girth
- On the strong chromatic index of sparse graphs
- On the precise value of the strong chromatic index of a planar graph with a large girth
- Additive bases and flows in graphs
- Colored homomorphisms of colored mixed graphs
- On deeply critical oriented graphs
- Nilpotent families of endomorphisms of ( P(V)^+,)
- Circular coloring of planar digraphs
- The game coloring number of planar graphs with a given girth
- On a list variant of the multiplicative 1-2-3 conjecture
- On fractional version of oriented coloring
- Odd graph and its applications to the strong edge coloring
- Complexity dichotomy for oriented homomorphism of planar graphs with large girth
- (d,1)-total labelling of planar graphs with large girth and high maximum degree
- On nice and injective-nice tournaments
- \(L(2,1)\)-labeling of oriented planar graphs
- An oriented 7-colouring of planar graphs with girth at least 7
- An oriented colouring of planar graphs with girth at least 4
- Exact square coloring of subcubic planar graphs
- Homomorphisms and colourings of oriented graphs: an updated survey
- Chromatic number of sparse colored mixed planar graphs
- Oriented and injective oriented colourings of grid graphs
- An oriented 6-coloring of planar graphs with girth at least 9
- An extension of Kotzig's theorem
- A note on circular chromatic number of graphs with large girth and similar problems
- Oriented vertex and arc colorings of partial 2-trees
- Girth and fractional chromatic number of planar graphs
- Homomorphism bounds for oriented planar graphs of given minimum girth
- On \(r\)-acyclic edge colorings of planar graphs
- Additive bases and flows in graphs
- Strong chromatic index of planar graphs with large girth
- The complexity of partitioning into disjoint cliques and a triangle-free graph
- Circular flows in planar graphs
- Homomorphism bounds for oriented planar graphs
- Some of my favorite coloring problems for graphs and digraphs
- scientific article; zbMATH DE number 2230325 (Why is no real title available?)
- Partitions of graphs into cographs
- On colouring oriented graphs of large girth
- The time complexity of oriented chromatic number for acyclic oriented connected subcubic subgraphs of grids
- Every triangulated 3-polytope of minimum degree 4 has a 4-path of weight at most 27
- On the oriented chromatic number of Halin graphs
- Oriented vertex and arc colorings of outerplanar graphs
- Optimal unavoidable sets of types of 3-paths for planar graphs of given girth
- Oriented colorings of partial 2-trees
This page was built for publication: Colorings and girth of oriented planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356774)
