✦ LIBER ✦

Characterization of graphs with hall number 2

✍ Scribed by Changiz Eslahchi; Matthew Johnson

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 165 KB
Volume: 45
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10154

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Hall's condition is a simple requirement that a graph G and list assignment L must satisfy if G is to have a proper L‐colouring. The Hall number of G is the smallest integer m such that whenever the lists on the vertices each has size at least m and Hall's condition is satisfied a proper L‐colouring exists. Hilton and P.D. Johnson introduced the parameter and showed that a graph has Hall number 1 if and only if every block is a clique. In this paper we give a forbidden‐induced‐subgraph characterization of graphs with Hall number 2. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 81–100, 2004

📜 SIMILAR VOLUMES

Threshold characterization of graphs wit

Threshold characterization of graphs with dilworth number two

✍ C. Benzaken; P. L. Hammer; D. de Werra 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 692 KB

A graph with nodes 1. \_.., n is a threshold signed graph if one can find two positive real numbers S,T and real numbers a , , ..., a, associated with the vertices in such a way that i,j are linked iff either la, + a,/ 3 S or la, -ail T. Such graphs generalize threshold graphs. It is shown that thes

Characterization of the graphs with boxi

Characterization of the graphs with boxicity ⩽2

✍ Martin Quest; Gerd Wegner 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 360 KB

The intersection graph of a family 8TI of sets has the sets in %' as vertices and an edge between two sets iff they have nonempty intersection. Following Roberts [4] the boxicity b(G) of a graph G is defined as the smallest d such that G is the intersection graph of boxes in Euclidean d-space, i.e.

Split graphs of Dilworth number 2

✍ C. Benzaken; P.L. Hammer; D. de Werra 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 250 KB

Graphs with least number of colorings

✍ A. Sakaloglu; A. Satyanarayana 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 535 KB

## Abstract A λ‐coloring of a graph G is an assignment of λ or fewer colors to the points of G so that no two adjacent points have the same color. Let Ω (n,e) be the collection of all connected n‐point and e‐edge graphs and let Ωp(n,e) be the planar graphs of Ω(n, e). This paper characterizes the g

Saturated graphs with minimal number of

Saturated graphs with minimal number of edges

✍ L. Kászonyi; Zs. Tuza 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB

Let F = {F,, . . .} be a given class of forbidden graphs. A graph G is called F-saturated if no F, E F is a subgraph of G but the addition of an arbitrary new edge gives a forbidden subgraph. In this paper the minimal number of edges in F-saturated graphs is examined. General estimations are given a

Graphs with small numbers of independent

Graphs with small numbers of independent edges

✍ Miroslav M. Petrović; Ivan Gutman; Mirko Lepović 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 327 KB

The graphs with exactly one, two or three independent edges are determined.