✦ LIBER ✦

Total colorings of planar graphs with large maximum degree

✍ Scribed by Borodin, O. V.; Kostochka, A. V.; Woodall, D. R.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 97 KB
Volume: 26
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199709)26:1<53::aid-jgt6>3.0.co;2-g

No coin nor oath required. For personal study only.

✦ Synopsis

It is proved that a planar graph with maximum degree ∆ ≥ 11 has total (vertex-edge) chromatic number ∆ + 1.

📜 SIMILAR VOLUMES

On total 9-coloring planar graphs of max

On total 9-coloring planar graphs of maximum degree seven

✍ Sanders, Daniel P.; Zhao, Yue 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 2 views

Given a graph G, a total k-coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If ∆(G) is the maximum degree of G, then no graph has a total ∆-coloring, but Vizing conjectured that every graph has a total (∆ + 2)-coloring. This Total Coloring Conjecture rem

(2 + ?)-Coloring of planar graphs with l

(2 + ?)-Coloring of planar graphs with large odd-girth

✍ Klostermeyer, William; Zhang, Cun Quan 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB 👁 1 views

The odd-girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function f ( ) for each : 0 < < 1 such that, if the odd-girth of a planar graph G is at least f ( ), then G is (2 + )-colorable. N

(n,e)-Graphs with maximum sum of squares

(n,e)-Graphs with maximum sum of squares of degrees*

✍ Peled, Uri N.; Petreschi, Rossella; Sterbini, Andrea 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB 👁 1 views

Among all simple graphs on n vertices and e edges, which ones have the largest sum of squares of the vertex degrees? It is easy to see that they must be threshold graphs, but not every threshold graph is optimal in this sense. Boesch et al. [Boesch et al., Tech Rep, Stevens Inst Tech, Hoboken NJ, 19

Constructing a bipartite graph of maximu

Constructing a bipartite graph of maximum connectivity with prescribed degrees

✍ Asano, Takao 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 328 KB 👁 1 views

d 2,n 2 ) is a bipartite graphical sequence, if there is a bipartite graph G with degrees {D 1 , D 2 } (i.e., G has two independent vertex sets In other words, {D 1 , D 2 } is a bipartite graphical sequence if and only if there is an n 1 1 n 2 matrix of 0's and 1's having d 1j 1 1's in row j 1 and

Constructions of large planar networks w

Constructions of large planar networks with given degree and diameter

✍ Fellows, M.; Hell, P.; Seyffarth, K. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB 👁 1 views

There is considerable interest in constructing large networks with given diameter and maximum degree. In certain applications, there is a natural restriction for the networks to be planar. Thus, consider the problem of determining the maximum number of nodes in a planar network with maximum degree D

Realizability of p-point, q-line graphs

Realizability of p-point, q-line graphs with prescribed maximum degree and line connectivity or minimum degree

✍ D. DiMarco 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 74 KB