Über den kartographischen Vierfarbensatz. (Mit 23 Figuren im Text)
Über endliche Graphen mit vorgegebenen Homomorphieeigenschaften.
Un nouveau type de preuve mathématique : le théorème des quatre couleurs. I - Exposé préliminaire
Un nouveau type de preuve mathématiques : II - Le théorème des quatre couleurs
Unified Spectral Bounds on the Chromatic Number
One of the best known results in spectral graph theory is the following lower bound on the chromatic number due to Alan Hoffman, where μ1 and μn are respectively the maximum and minimum eigenvalues of the adjacency matrix: χ ≥ 1+μ1/−μn. We recently generalised this bound to include all eigenvalues of the adjacency matrix. In this paper, we further generalize these results to include all eigenvalues of the adjacency, Laplacian and signless Laplacian matrices. The various known bounds are also unified...
Uniform edge distribution in hypergraphs is hereditary.
Unique factorization theorem
A property of graphs is any class of graphs closed under isomorphism. A property of graphs is induced-hereditary and additive if it is closed under taking induced subgraphs and disjoint unions of graphs, respectively. Let ₁,₂, ...,ₙ be properties of graphs. A graph G is (₁,₂,...,ₙ)-partitionable (G has property ₁ º₂ º... ºₙ) if the vertex set V(G) of G can be partitioned into n sets V₁,V₂,..., Vₙ such that the subgraph of G induced by Vi belongs to ; i = 1,2,...,n. A property is said to be reducible...
Unique factorization theorem for object-systems
The concept of an object-system is a common generalization of simple graph, digraph and hypergraph. In the theory of generalised colourings of graphs, the Unique Factorization Theorem (UFT) for additive induced-hereditary properties of graphs provides an analogy of the well-known Fundamental Theorem of Arithmetics. The purpose of this paper is to present UFT for object-systems. This result generalises known UFT for additive induced-hereditary and hereditary properties of graphs and digraphs. Formal...
Uniquely edge colourable graphs
Uniquely -colorable and chromatically equivalent graphs.
Uniquely partitionable graphs
Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph induced by has property ; i = 1,...,n. A graph G is said to be uniquely (₁, ...,ₙ)-partitionable if G has exactly one (₁,...,ₙ)-partition. A property is called hereditary if every subgraph of every graph with property also has property . If every graph that is a disjoint union of two graphs that have property also has property , then we...
Unique-Maximum Coloring Of Plane Graphs
A unique-maximum k-coloring with respect to faces of a plane graph G is a coloring with colors 1, . . . , k so that, for each face of G, the maximum color occurs exactly once on the vertices of α. We prove that any plane graph is unique-maximum 3-colorable and has a proper unique-maximum coloring with 6 colors.
Unit distance graphs with ambiguous chromatic number.
Unit-distance graphs, graphs on the integer lattice and a Ramsey type result.
Upper bounds on the b-chromatic number and results for restricted graph classes
A b-coloring of a graph G by k colors is a proper vertex coloring such that every color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k-1 color classes. The b-chromatic number is the maximum integer k for which G has a b-coloring by k colors. Moreover, the graph G is called b-continuous if G admits a b-coloring by k colors for all k satisfying . In this paper, we establish four general upper bounds on . We present results on the b-chromatic number...
Upper bounds on the non-3-colourability threshold of random graphs.
Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs
The oriented chromatic number of an oriented graph is the minimum order of an oriented graph such that admits a homomorphism to . The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph such that every orientation of G admits a homomorphism to . We give some properties...